Big-O 표기법에서 다음 방법의 시간 복잡도는 어떻게됩니까?

Question

저 여기에서는이 방법의 시간 복잡도를 해결 :

void method(int n, int[] array) 
{ 
    int i = 0, j = 0; 

    for(; i < n; ++i) 
    { 
    while(j < n && array[i] < array[j]) 
    { 
     j++; 
    } 
    } 
} 

Answer 1

런타임은 O (N)이다.

외부 루프의 일부 반복에서는 내부 루프가 여러 번 진행될 수 있고 다른 루프에서는 전혀 진행되지 않을 수도 있지만 총 최대 n 개가 증가하여 j이됩니다. 이것은 (i의 값이) 어떤 일이 발생하는지에 관계 없기 때문에, j의 (최대) n 증가에 대한 O (n) + O (n)이라고 말할 수 있습니다. O (n) + O (n) = O (n).

이는 외부 루프의 각 반복위한 내부 루프 의 n 반복 수행함으로써 O (n)이 될 전형적인 '루프 내부 루프'에 반하는 * O (N) = O (N^2).