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

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

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

물리적 물체 나 속성이 원칙적으로 일련의 비트, 개체 및 속성에 의해 근접한 exhaustion에 설명 될 수 있기 때문에알고리즘 복잡성도 갖는 데 도움이됩니다. 실제로, 실제 객체의 복잡성을 객체를 출력으로 생성하는 프로그램으로 줄이는 것은 과학 기업을 보는 한 가지 방법입니다. 우리 주변의 복잡한 대상은 세 가지 주요 생성 프로세스에서 나오는 경향이 있습니다. 출현 , evolution 및 인텔리전스 .

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

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