-2
병합 정렬의 시간 복잡도를 분석 할 때 O (log (n)) 수준이 있고 각 수준에서 O (n) 연산이 필요하므로 전체 시간 복잡성은 O (nlog .mergesort 복잡성 O (nlogn) + O (n)?
그러나 O (n) 합계를 나누지 않습니까? 요소 집합의 각 나누기는 O (1)을 취하지 만 합계 O (n) 번을 나누면 병합 정렬의 나누는 부분이 O (n)을 차지하지 않습니까? 예를 들어, 8 개의 원소가 있다면 7 번으로 나눠야하고, 16 개의 원소가 있다면 15 번으로 나눠야합니다.
따라서 전체 병합 정렬 시간의 복잡성을 기술적으로 O (nlog (n)) + O (n)로해서는 안됩니까? 나는 O (nlog (n) + n)이 O (nlog (n))와 같은 것이라는 것을 알고 있지만 병합 정렬 시간의 복잡성에 대해서는 아무도 언급하지 않는 것으로 보인다.
당신은 그들이 동일하다는 것을 알고 있습니다. 그러나 아무도 그렇게 말하지 않는 이유를 이해하지 못합니까? –
나는 O (n) 인 삭제 과정에 대한 나의 논리가 결함이 있을지 모르기 때문에 O (n) 인 삭제 부분에 대해서는 아무 것도 볼 수 없기 때문에 결함이있을 수 있다고 생각하고있다. – David
그건 당신이 요구 한 것이 아닙니다. O (n log n) 알고리즘에서 O (n) 용어가 무시 된 이유를 물었고 다른 O-n (n log n) (예 : O 1)과 같은 이유가 무시되었습니다. 설명했고 당신은 이미 이해한다고 주장합니다. –