누군가가 나에게 무엇을 할 지 설명 할 수 있습니까?

Question

나는 대답을 원합니다. 어떻게하는지 알고 싶습니다. 알고리즘 doIt의 효율성은 O (f (n)) = n^3으로 표현할 수 있습니다. 다음 프로그램 세그먼트의 효율성을 정확히 계산하고 big-O 표기법을 사용합니다.

for (i=1; i<=n+1; i++) 
    for (j=1; j<n, j++) 
     doIt (...) 

그가 우리는 그가 단지 내부는 중첩 루프 것을 우리에게 보여 주었다 다른 사각형의 여러 사각형을 끌었다 이런 건 아니었다 준 예. 그는 우리에게 문제의 코드와 같은 어떤 종류의 코드도주지 않았습니다. 그는 단지

Δ1g의 (m, N, K, L) = 3N^3
M = 1N, N = 1 2N 쓴 K는 = 1N, L = 1 N^2
N^2 * N * 2n * n * 3n^3 = 6n^8 = O (n^8)

이렇게 중첩 된 루프이고 최대 값은 n^3이라고 가정합니다. 다른 사람들이 예제 코드를 작성하여 더 잘 이해할 수 있습니까?

Answer 1

for (i=1; i<=n+1; i++) 
for (j=1; j<n, j++) 
    doIt (...) 

최악의 경우 복잡성은 O (n^3)입니다.

중첩 된 루프의 경우 주요 관심사는 첫 번째 루프가 내부 루프를 안내한다는 것입니다. 즉, 내부 루프는 일반적으로 아니오를 실행합니다. 반복 (절대 항상은 아님)의 바깥 쪽 루프보다!

질문에 따라 바깥 쪽 루프는 i = 1에서 i = n + 1 --- n+1 times까지 실행됩니다. 마찬가지로 내부 루프는 외부 루프의 각 반복에서 j = 1에서 j < n --- n-1 반복 실행됩니다. 또한 doIt() 함수는 복잡도가 O (n^3) 인 내부 루프 내부에 있습니다.

다음으로 n + 1 회 반복은 최악의 경우의 복잡도에 따라 O (n) 차수입니다.

마찬가지로 n-1 회 반복은 최악의 경우의 복잡도에 따라 O (n)의 차수입니다.

따라서, 당신이 이해 할 수없는 경우 아래의 코멘트를 남겨주세요

전체 최악의 복잡성 = O(n)*O(n)*O(n^3) = O(n^5) ...!