알고리즘 복잡성이란 무엇입니까?

알고리즘 복잡도 (계산 복잡도 또는 Kolmogorov 복잡도)는 계산 복잡도 이론 및 알고리즘 정보 이론 모두에서 기본 아이디어이며 공식 유도에서 중요한 역할을합니다.

이진 문자열의 알고리즘 복잡도는 문자열을 생성 할 수있는 가장 짧고 가장 효율적인 프로그램으로 정의됩니다. 주어진 문자열을 생성 할 수있는 무한한 수의 프로그램이 있지만 하나의 프로그램 또는 프로그램 그룹이 항상 가장 짧습니다. 주어진 문자열을 출력하는 가장 짧은 알고리즘을 찾는 알고리즘적인 방법은 없습니다. 이것은 계산 복잡도 이론의 첫 번째 결과 중 하나입니다. 그럼에도 불구하고 우리는 교육적인 추측을 할 수 있습니다. 이 결과 (문자열의 계산 복잡도)는 계산 가능성과 관련된 증거에 매우 중요합니다.

임의의 물리적 객체 또는 속성은 원칙적으로 일련의 비트에 의해 거의 소진되는 것으로 설명 될 수 있기 때문에, 객체 및 속성은 알고리즘 복잡도를 갖는다 고 말할 수있다. 실제로, 실제 객체의 복잡성을 감소시켜 출력으로 객체를 생성하는 프로그램은 과학 기업을 보는 한 가지 방법입니다. 우리 주변의 복잡한 물체는 세 가지 주요 생성 과정에서 오는 경향이 있습니다. 각각에 의해 생성 된 객체가 더 큰 알고리즘 복잡성을 향한 출현 , 진화 및 지능 .

계산 복잡도는 이론적 컴퓨터 과학에서 널리 사용되는 개념으로 광범위한 수학 및 논리 문제에 대한 솔루션 계산의 상대적 어려움을 결정합니다. 400 개 이상의 복잡한 클래스가 존재하며 추가 클래스가 지속적으로 발견되고 있습니다. 유명한 P = NP 문제는이 두 가지 복잡성 클래스의 특성에 관한 것입니다. 복잡성 수업에는 수학에서 미적분학까지 직면 할 수있는 것보다 훨씬 어려운 문제가 포함됩니다. 계산 복잡도 이론에는 상상할 수있는 많은 문제가 있으며, 해결하는데 거의 무한한 시간이 걸립니다.

알고리즘 복잡성 및 관련 개념은 1960 년대 수십 명의 연구자들에 의해 개발되었습니다. Andrey Kolmogorov, Ray Solomonoff 및 Gregory Chaitin은 60 년대 후반 알고리즘 정보 이론을 통해 중요한 기여를했습니다. 알고리즘 복잡성과 밀접한 관련이있는 최소 메시지 길이의 원칙은 통계 및 귀납적 추론 및 기계 학습의 기초를 제공합니다.