코드 세그먼트의 Big-Oh를 찾는 방법을 이해하는 데 도움이 필요합니다.

Question

My Computer Science II final이 내일입니다. 코드 세그먼트에 Big-Oh를 찾는 방법을 이해하는 데 도움이 필요합니다. 나는 인터넷을 수색했는데 어떻게 이해해야하는지 예를 찾을 수 없었다. 우리는 알고리즘의 순서 (빅 - 오)를 찾기 위해 해야하는

for(int pass = 1; i <= n; pass++) 
{ 
    for(int index = 0; index < n; index++) 
     for(int count = 1; count < n; count++) 
     { 
      //O(1) things here. 
     } 
    } 
} 

:

여기에 최종 우리의 샘플에서 문제입니다.

여기이 될 것이다 O (N^3)을 생각하고, 내가 제대로하고있어 경우에 그냥 모르겠어요 결론

for(int pass = 1; i <= n; pass++) // Evaluates n times 
{ 
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
     for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
     { 
      //O(1) things here. 
     } 
    } 
} 
// T(n) = (n) + (n^2 + n) + n^3 
// T(n) = n^3 + n^2 + 2n 
// T(n) <= c*f(x) 
// n^3 + n^2 + 2n <= c * (n^3) 
// O(n) = n^3 

에 온 방법이다. 누군가 이처럼 코드를 평가하고 /하거나 내 대답을 확인하는 방법을 설명 할 수 있습니까?

Answer 1

예, O(n^3)입니다. 그러나 : 합계가 n^3 - n^2 상수를 가지고 있도록 루프에 대한 중첩의 세 개의 층을 가지고 있기 때문에

for(int pass = 1; pass <= n; pass++) // Evaluates n times 
{     //^^i should be pass 

    for(int index = 0; index < n; index++) //Evaluates n times 
     for(int count = 1; count < n; count++) // Evaluates n-1 times 
     { 
      //O(1) things here. 
     } 
    } 
} 

중첩 루프는 루프의 가장 안쪽 내부 n *n * (n-1) 회, 각 동작을 평가한다는 O (1) 시간이 걸린다 증가 순서대로 O(n^3)입니다.

큰 O 표기법 성장의 순서를 측정하는 방법의 좋은 요약은 여기에서 찾을 수 있습니다 : 위의 파일에서 일부를 인용

Big O Notation MIT

:

중첩는

루프

for I in 1 .. N loop 
    for J in 1 .. M loop 
     sequence of statements 
    end loop; 
end loop; 

외부 루프는 N 번 실행됩니다. 외부 루프가 실행될 때마다 내부 루프 이 M 번 실행됩니다. 결과적으로 내부 루프의 문은 총 N * M 번을 실행합니다. 따라서 복잡성은 O (N * M)입니다. 내부 루프의 정지 조건이 인 대신에 (즉, 내부 루프도 N 번 실행되는) 일반적인 루프의 경우 두 루프의 총 복잡성은 O (N^2)입니다.

비슷한 이유가이 경우에 적용될 수 있습니다.

Answer 2

귀하는 틀림이 없습니다. 예를 들어 O (n^3)입니다.

어떤 코드 세그먼트의 Big Oh 실행 시간을 찾으려면 코드 조각이 O (1) 개를 수행하는 횟수를 생각해야합니다.

날이의 더 나은 아이디어를 제공하기 위해 예를 단순화하자 : 위의 경우

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times 
    { 
     //O(1) things here. 
    } 
} 

를, 내부 루프는 외부 루프의 각 실행에 대한 n 배를 실행합니다. 그리고 외부 루프도 n 번 실행됩니다. 이것은 당신이 n 가지를하고 있음을 의미합니다. 그것을 O (n^2)로 만듭니다.

다른 하나는 Big Oh가 상한선입니다. 즉, 큰 입력 (큰 경우, n)이있을 때 코드에 어떤 일이 생길지 항상 생각해야합니다.이 사실의 또 다른 함축은 상수에 의한 곱셈 또는 덧셈은 Big에 아무런 영향을 미치지 않는다는 것입니다 . 오 예 행 :

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times 
    for(int count = 1; count < 2*n; count++) // Runs 2*n times 
    { 
     //O(1) things here. 
    } 
} 

코드의 큰 오 실행 시간도 O (N^2) O (n 개 * (2N)) = O (N^2) 이후

. 또한 이것을 확인하십시오 : http://ellard.org/dan/www/Q-97/HTML/root/node7.html