이 코드의 복잡성은 어떻게됩니까? 복잡성을 더해야합니까?

Question

나는 처음에는 벡터를 정렬 한 다음 그 요소를 반복하고 XOR 알고리즘을 가지고 있습니다. 전체 알고리즘의 복잡성을 계산하기 위해 sort 및 for 루프의 복잡성을 합산해야합니까?

std::sort(array.begin(), array.end()); 
for (int i =1; i < array.size(); ++i) { 
    result = array[i-1]^array[i]; 
} 

우리는 O(N) 복잡성과 평균 O(N log N) 비교가 std::sort을 가지고 루프를 가지고 : 그래서, 나는 다음 코드가 있습니다. 다음 코드의 복잡도는 O(N + N log N)입니까? 또는이 경우 선형 시간 인 O(N log N) 인 최고 시간 복잡도 클래스를 선택하고 합계하지 마십시오.

Answer 1

런타임은 정렬 단계 O(nlgn) 의해 제한되는 것으로한다 O(N log N) + O(N)이다. for 루프의 복잡도는 O(n) 일 수 있지만 전체 런타임은 항상 최고 전력이 지배합니다. 수학적 증명 여기를 참조하십시오 :

https://math.stackexchange.com/questions/324200/big-o-notation-sum-rule

Answer 2

복잡도 클래스 O(N)은 O(N log N) 클래스의 하위 집합으로, log N > 1이 충분히 높으므로 N입니다. 따라서 코드 O(N + N log N)의 복잡성 등급은 O(2 N log N)의 하위 집합이며 복잡도 등급은 불변의 w.r.t입니다. 상수는 O(N log N) 끝에 있습니다.

Answer 3

우리가 복잡성을 계산하는 방법은 모든 것들 중에서 가장 높은 것을 선택하는 것입니다.

그래서, 당신은 여기가 복잡성은 O(n^2) + O(n)이 될 것입니다, 그래서 다음 코드

for i in range 0 to n 
{ 
    for in range 0 to n 
    { 
     \\ code 
    } 
} 

for i in range 0 to n 
{ 
    \\ code 
} 

이 있다고 가정 할 수 있습니다. 마침내 O(n^2)이 될 것입니다. 따라서 위 코드 전체의 복잡도는 O(n^2)입니다.

---

유사 사건의 복잡성은 최종 복잡성 O(N log N)

Answer 4

예, 당신이 그들을 요약 할 수 있습니다 O(n) 및 O(n log n)이 O(n + n log n)된다. 그러나 덧셈은 기본 산술 연산에서 곱하기 이후에 제공되므로 이 아니라O(2n log n)입니다. 고독한 n 용어가 n log n 기간보다 작은 때문에

이제 그냥 O(1 + n) 항상 O(n)로 감소, 당신의 O(n + n log n)는 O(n log n)로 감소되며, 큰 O 표기법은 제한하지 정확한 방정식에 대해 항상이다.

어떤 사람들은 O(n)이 O(n log n)에 의해 지배되고 처음에는 합계되지 않는다는 것을 처음부터 인식하는 것이 더 직관적이라고 생각할 수도 있습니다. 그것은 유용한 정신 지름길이지만 두 가지 관점 모두 당신에게 같은 결과를 가져옵니다.

Answer 5

우선 O(N+N log N)은 O(2N log N)이 아니며, O((log N+1) * N)입니다. 이 알고리즘은 O(N log N)으로 제한됩니다. N이 무한대에 가까워 질수록 O(N)보다 빠르게 커집니다.