힙의 알고리즘 시간 복잡도

Question

위키 백과에 표시된이 힙 알고리즘의 시간 복잡도가 정확히 무엇인지 말해 줄 수 있습니까? https://en.wikipedia.org/wiki/Heap%27s_algorithm?

여러 웹 사이트를 검색했으며 답변이 모호합니다. 일부는 시간 복잡도가 O (N!)이고 일부는 O (NlogN)라고 말합니다. 어느 것이 정답입니까? 그리고 왜?

감사합니다.

Answer 1

N! 순열과 모든 생성은 Θ (N!) 시간과 Θ (N) 공간을 필요로합니다. 즉, 각 순열은 상각 된 Θ (1) 시간을 필요로합니다.

위 사실은 위키 피 디아 페이지에 제시된 재귀 알고리즘에서 파생 될 수 있습니다. 본질적으로 코드는 스왑과 출력을 번갈아 수행하므로 각 출력에는 단일 스왑이 포함됩니다.

그러나 호출 작업과 루프 테스트도 있습니다. 각 호출 전에 단일 루프 테스트가 있으므로 전체 호출 수를 계산하면됩니다.

최악의 경우 출력 전에 n 재귀 호출이 발생합니다. 그러나 알고리즘의 시작 부분에 한 번만 발생합니다. 인수가 인 단일 호출이 인 경우 n이 생성됩니다. 출력. 그것은 각각 n 재귀 호출로 이루어지며, 각각은 (n-1)을 생성합니다! 출력 및 수행 ( N-1) 재귀 호출하므로 N (N -1) 인수 N -2로 호출있다. 등의 곳 있도록 1 + N + N ( N-1) + N ( N-1) (N -2) + ... + n! 전화. 쓸 수

Σ 같은 I ≤ N N!/I ! 또는 (Σ I ≤ N 1/I !) N! 또는 (e-1), 약 1.71828 n입니다!

Answer 2

힙의 알고리즘과 힙 코드 알고리즘 또는 힙 데이터 구조가 혼란 스럽다고 생각합니다. 나중의 두 개는 정렬을위한 O (NlogN)의 복잡성을 가지고 있습니다.

언급 한 알고리즘은 모든 순열을 생성하기위한 것이며 N! 모든 N 요소 배열에 대한 순열, 복잡성은 O (N!)입니다.