BIG-O 복잡성을위한 수행 코드 분석을 결정할 수있는 도구가 있습니까?

Question

나는 거기에서 아무것도 보지 못했고, 일반적으로 복잡한 기능을 분석하기 위해서는 "n"을 정의하는 데 어려움이 있다고 생각합니다.

사이클러성 복잡성을위한 분석 도구가 있지만 시간 (및/또는 공간) 복잡성이 있습니까? 그렇다면 어느 것이 아니라면, 왜 그렇지 않습니까? 불가능합니까? 불가능한? 누군가가 그것에 도착하지 않았습니까?

이상적으로는 응용 프로그램에 대한 전반적인 복잡성 (다른 가능한 "n"을 정의하는 것과 앱의 각 방법에 대한 것과 같은 것이 있습니다.

편집 : 따라서 정확한 솔루션이 불가능한 것 같습니다. 중단 문제 그러나 어떤 종류의 휴리스틱 근사치가 가능합니까? 실용적인 목적을 위해 좋은 프로파일 러는 훨씬 더 유용한 정보를 줄 것이지만 흥미로운 문제처럼 보입니다.

또한 특정 서브 세트를 계산하는 것은 어떻습니까?

Answer 1

불행히도이 문제가 있습니다 중단 문제...

Answer 2

아니요, 중단 문제로 인해 불가능합니다.

응용 프로그램을 개선하기 위해이 작업을 수행하려면 대신 프로파일 링을 고려할 수 있습니다. 실제로 가장 많은 시간이 걸리는 것을 고정시킬 수 있습니다. 이렇게하면 작은 데이터 세트에서만 실행되는 O (n^3) 알고리즘을 최적화하는 데 시간을 소비하지 않습니다.

Answer 3

몇 가지 그래도 :

실제 컴퓨터는 대략 결정적인 유한 상태 기계이므로 중단 문제는 실제로 실제 제한이 아닙니다. 실질적인 제한은 대기하는 것보다 더 많은 시간이 걸리는 알고리즘입니다.

알고리즘의 복잡성에 대한 대략적인 아이디어를 얻으려면 언제든지 임의의 입력 세트에서 실행하고 취한 시간을 측정 할 수 있습니다. 그런 다음 데이터를 통해 곡선을 플로팅하십시오.

알고리즘의 시간 복잡성을 분석하는 것은 상당히 복잡하여 몇 가지 창의적인 단계가 필요합니다. (예 : QuickSort 분석을 참조하십시오). 문제는 논리 정리 증명 및 프로그램 검증과 밀접한 관련이 있습니다. 반자동 복잡성 솔루션, 즉 인간의 힌트가 주어진 솔루션을 체계적으로 검색하는 도구 인 유용한 도구를 구성하는 것이 가능할 수 있지만 쉽지는 않습니다.

Answer 4

이 작업을 수행하는 도구를 본 적이 없지만 프로파일 링 도구를 사용하여 병목 현상이 어디에 있는지 더 잘 알 수 있습니다. 항상 명백한 것은 아니며 실제로는 오랜 시간이 걸렸다 고 생각한 것들로 인해 몇 번이나 놀랐습니다. .NET 세계에서는 사용했습니다 개미 그리고 제트 브레인 도구.