콜모고로프 복잡도

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이의 데이터 열에 복잡성을 나타내는 지표중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최소값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고르프의 이름을 따서 지었다..[1][2]

이 그림은망델브로 집합 프랙탈의 일부를 나타낸다. 이 그림의 각각의 픽셀의 24비트 색상을 저장하는 것만 해도 백62만 비트가 필요하다. 하지만 작은 컴퓨터 프로그램이 망델브로 집합의 정의를 사용하여 표현할 수 있으며 이미지의 코너를 조정할 수 있다. 그러므로 이 그림을 인코딩한 비압축 파일의 코모고르프 복잡성은 162만 보다 작다.

주석[편집]

  1. Kolmogorov, Andrey (1963년). On Tables of Random Numbers. 《Sankhyā Ser. A.》 25: 369–375. MR178484.
  2. Kolmogorov, Andrey (1998년). On Tables of Random Numbers. 《Theoretical Computer Science》 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR1643414.

바깥 고리[편집]