각 코드 줄의 Big Oh를 파악하고 싶었습니다. 처음 두 줄을 얻을 수 있었지만 세 번째 줄이 혼란 스럽습니다.
sum <- 0 // O(1)
for i <- 0 to n do // O(n + 3)
for j <- 0 to i * i do //
for k <- 0 to j do //
sum <- sum + 1 //
{ k <- k + 1 } //
{ j <- j + 1 } //
{ i <- i + 1 }
sum <- 0 // O(1)
for i <- 0 to n do // O(n)
for j <- 0 to i * i do // O(n^2), this means that last/longest run (when i==n) of this inner loop will take n*n iterations
for k <- 0 to j do // O(n^2), last run of this loop (j==i*i==n^2) will take n^2 iterations
sum <- sum + 1 // O(1)
{ k <- k + 1 } // O(1)
{ j <- j + 1 } // O(1)
{ i <- i + 1 } // O(1)
내부 (k) 루프로 시작할 수 있습니다. 가장 긴 실행은 무엇입니까? j가 최대 일 때? max J = maxI * maxI = n ^ 2, 따라서 내부 (k) 루프의 공평성은 O (N ^ 2)입니다.
K 루프는 몇 번 실행됩니까? 다시 N ^ 2이므로 J 루프의 복잡도는 N ^ 2이고,이 두 루프의 총 복잡도는 다음과 같습니다. O (J 루프 * O (K 루프)) = O (N ^ 2 * O (N ^ 2)) = O ( N ^ 4)
마지막-외부 I 루프가 있고 복잡성은 O (N)이므로 최종 합계가 있습니다.
O (n * O (n ^ 2 * O (n ^ 2))) = O (n ^ 5)
그래서 기본적으로 우리는 위쪽 점근선을 찾기 위해 "최악의"경우를 확인합니다. 즉,이 알고리즘의 실행 시간은 n ^ 5가 증가함에 따라 같은 속도로 증가합니다.
참고 :
이 루프의 복잡성 :
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
N ^ 2입니다.
거의 동일한 루프 (하지만 두 번째 조건에주의) :
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
이것의 복잡성도 N ^ 2입니다. 조금 더 빨리 실행될 것이 분명하더라도 N ^ 2가 증가하면 전체 실행 시간이 늘어납니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다