나는 생성 된 몇 가지 알고리즘에서 최악의 런타임 복잡도 순서를 얻으려고합니다. 그러나 알고리즘에 대한 기본 작업의 잘못 또는 잘못된 양을 선택하는 경향이있는 문제가 발생했습니다.런타임 복잡도를 계산할 때 기본 작업을 어떻게 알 수 있습니까?
나에게 그것은 근본적인 작동의 선택이 과학보다 더 예술적인 것처럼 보입니다. 인터넷 검색을하고 텍스트 상자를 읽은 후에도 여전히 좋은 정의를 찾지 못했습니다. 지금까지 필자는이를 "알고리즘 실행 내에서 항상 발생하는 연산"(비교 또는 배열 조작과 같은)으로 정의했습니다.
그러나 알고리즘에는 항상 많은 비교가 항상 실행되므로 어떤 작업을 선택합니까?
나는 그것이 어느 정도 예술에 동의하므로 항상 문서 작성 등을 명확히해야합니다.하지만 일반적으로 기본 데이터 구조에 대한 "방문"입니다. 당신이 말했듯이 배열의 경우 비교 또는 스왑, 해시 맵의 경우 키의 수동 검사 일 수도 있고 그래프의 경우 꼭지점이나 가장자리를 방문하는 것일 수도 있습니다.
이것은 작동합니다 알고리즘을 실제로 구현했지만 어떤 작업이 병목인지 알기 위해 프로파일 러를 사용할 수 있습니다. 그것은 실용적인 관점입니다. 이론적으로 어떤 사람들은 기본 작업이 아닌 모든 작업이 0 시간에 실행된다고 가정합니다.
에도 연습 복잡성 이론가들은 이런 종류의 물건에 대한 의견 차이를 가지고, 그래서 다음은 조금 주관적 일 수 있습니다 http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html는
큰 O 표기법의 목적은 독자 알고리즘의 효율성을 요약하는 것입니다. 실용적인 맥락에서 볼 때 big-O 상수가 극도로 작거나 크지 않다는 가정하에 (그리고 메모리 계층 구조의 영향을 무시하고) 알고리즘이 얼마나 많은 클록주기를 갖는지에 가장 관심이 있습니다. 이것은 링크 된 게시물에서 언급 된 "단위 비용"모델입니다.
정렬 알고리즘에 대한 비교를 계산하는 이유는 비교 비용이 입력 데이터의 유형에 달려 있기 때문입니다. 정렬 알고리즘은 O (c n log n) 사이클을 소요한다고 말할 수 있는데, 여기서 c는 비교 비용이지만 알고리즘에 의해 수행 된 다른 작업은 O (n log n)이기 때문에 비교를 계산하는 것이 더 간단합니다. n^2 log n steps과 n^2 비교에서 길이 n 인 n 개의 정렬 된 배열의 연결을 정렬하는 정렬 알고리즘이 있습니다. 여기서는 비교 수와 계산 오버 헤드가 따로 명시되어 있지 않기 때문에 다른 수문을 지배하지 않기 때문에 별도로 명시해야합니다.
는내가 들었 다소 단순한 정의는 다음과 같습니다
알고리즘의 다른 작업으로 적어도 여러 번 실행되는 작업.
예를 들어 정렬 알고리즘에서 재 배열하기 전에 거의 항상 요소를 방문하고 '확인'해야하므로 할당보다는 비교가되는 경향이 있지만 확인이 재주문. 따라서 과제와 비교할 때 항상 많은 비교가 이루어집니다.