함수 내의 함수를 사용한 Big-O 분석

Question

함수 내에서 함수를 처리 할 때 Big-O가 작동하는 방법에 대해 혼란 스럽습니다 (최악의 경우를 분석 할 때). 예를 들어, 같은 것을 어떤이있는 경우 :

for(int a = 0; a < n; a++) 
{ 
    *some function that runs in O(n*log(n))* 
    for(int b = 0; b < n; b++) 
    { 
     *do something in constant time* 
    } 
} 

겠습니까 O이 전체 블록 실행 (N^2 * 로그 (N)), 루프에 대한 첫 번째 내에서, 당신은 O (n)을 가지고 있기 때문에 O (n * log (n))이므로 O (n * log (n))가 더 큽니다. 또는 외부 for 루프 내에 O (n) 및 O (n * log (n))가 있으므로 O (n^3 * log (n))입니까?

도움을 주시면 감사하겠습니다. 감사! 당신이 O(N lg N) 기능의 O(N) 반복하고 O(N) 일정 시간 작업을 가지고 있기 때문에

Answer 1

이

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N)) 
           = O(N) * O(N lg N) 
           = O(N^2 lg N) 

을합니다. O(N lg N) + O(N)은 O(N lg N)으로 단순화되어 있기 때문에 O(N lg N) > O(N)입니다.

Answer 2

이 유형의 복잡도를 계산할 때는 을 인라인 또는 순차 함수에 추가하고 에 중첩 함수를 곱하면됩니다.

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed) 
for (int i = 0; i < n; i++) 
{ 
    /* something constant */ 
} 
for (int j = 0; j < n; j++) 
{ 
    /* something constant */ 
} 

을하지만 기능이 중첩 될 때, 복잡성 곱 :

예를 들어,이 O(n) 것

// O(n) * O(n) = O(n^2) 
for (int i = 0; i < n; i++) 
{ 
    for (int j = 0; j < n; j++) 
    { 
     /* something constant */ 
    } 
} 

당신의 예는 조합입니다 - 당신은 어떤 연속 작업이 있어요 다른 함수 안에 중첩됩니다.

// this is O(n*logn) + O(n), which is O(n*logn) 
*some function that runs in O(n*log(n))* 
for(int b = 0; b < n; b++) 
{ 
    *do something in constant time* 
} 

// multiplying this complexity by O(n) 
// O(n) * O(n*logn) 
for(int a = 0; a < n; a++) 
{ 
    // your O(n*logn) 
    // your b loop 
}