이 알고리즘의 Big-O 복잡성이 O (n ^ 2) 인 이유는 무엇입니까?

이 알고리즘의 Big-O 복잡성이 O (n ^ 2) 인 이유는 무엇입니까?

---

이 알고리즘의 큰 O 복잡성이라는 것을 알고 O(n^2)있지만 그 이유를 이해할 수 없습니다.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

j = n * n처음에 설정했지만 반복 할 때마다 i를 증가시키고 j를 감소 시키므로 결과 반복 횟수가 n*n? 보다 훨씬 적 으면 안됩니다 .

---

반복 할 때마다 증가 i하고 감소합니다. j이는 단지 i2 씩 증가 하는 것과 같습니다 . 따라서 총 반복 횟수는 n ^ 2 / 2이고 여전히 O (n ^ 2)입니다.

---

big-O 복잡도는 계수를 무시합니다. 예 : O(n),, O(2n)및 O(1000n)모두 동일한 O(n)실행 시간입니다. 마찬가지로, O(n^2)그리고 O(0.5n^2)모두 O(n^2)실행 시간.

(이후 상황에서, 당신은 기본적으로 루프를 통해 2 때마다 루프 카운터를 증가하고 j--같은 효과 등이있다 i++). 따라서 실행 시간은 O(0.5n^2)이지만 O(n^2)계수를 제거 할 때 와 동일 합니다.

---

당신은 정확히 n*n/2루프 반복을 할 것입니다 (또는 홀수 인 (n*n-1)/2경우 n). Big O 표기법에서 우리는 O((n*n-1)/2) = O(n*n/2) = O(n*n)상수 인자가 "계산되지 않기"때문입니다.

---

귀하의 알고리즘은

while (i += 2 < n*n) 
  ...

이는 O(n^2/2)동일한되는 O(n^2)큰 O 복잡성이 상수 신경 쓰지 않기 때문에.

---

m을 반복 횟수라고합시다. 그때,

나는 + m = n ^ 2-m

주는,

m = (n ^ 2-i) / 2

Big-O 표기법에서 이것은 O (n ^ 2)의 복잡성을 의미합니다.

---

예,이 알고리즘은 O (n ^ 2)입니다.

복잡성을 계산하기 위해 복잡성 표가 있습니다.

O (1) O (log n) O (n) O (n log n)
O (n²) O (n ^ a) O (a ^ n) O (n!)

각 행은 알고리즘 세트를 나타냅니다. O (1), O (n), O (n ^ 2) 등에있는 알고리즘 세트입니다. 그러나 그 반대는 아닙니다. 따라서 알고리즘은 n * n / 2 문장을 실현합니다.

O (n) <O (nlogn) <O (n * n / 2) <O (n²)

따라서 알고리즘의 복잡성을 포함하는 알고리즘 세트는 O (n²)입니다. O (n) 및 O (nlogn)이 더 작기 때문입니다.

예 : To n = 100, sum = 5000. => 100 O (n) <200 O (n · logn) <5000 (n * n / 2) <10000 (n ^ 2)

영어로 미안합니다.

---

처음에 j = n * n을 설정했지만, 반복 할 때마다 i를 증가시키고 j를 감소 시키므로 결과 반복 횟수가 n * n보다 훨씬 작아야하지 않습니까?

예! 그래서 O (n ^ 2)입니다. 같은 논리로, 보다 훨씬 작기 n * n * n때문에 O (n ^ 3)이됩니다. 비슷한 논리로 O (6 ^ n)입니다.

big-O는 상한에 대한 정보를 제공합니다.

난 당신이 복잡 세타 (N) 또는 오메가 (n)의 이유를 물어하려고 생각하지만, 그냥 큰 O가 무엇인지 이해하려고 노력하는 경우, 당신은 정말 그것을주는 것을 이해할 필요가 상한을 제 기능에 맨 먼저.

참조 URL : https://stackoverflow.com/questions/33858889/why-is-the-big-o-complexity-of-this-algorithm-on2