알고리즘 시간 복잡도 분석 (내부 while 루프가있는 루프의 경우)

Question

다음은 간단히 구현 한 코드입니다. for 루프는 O (n)의 복잡성을 가져야합니다. 나는 내부 while 루프의 시간 복잡성을 파악할 수 없다.

int x,n;  // Inputted by the user. 
for (int i=0; i<n; i++) 
{ 
    int done=0; 
    if (Condition) 
    { 

     while (done < x) 
     { 
      done++;  // Based on a lot of operations 
     } 
    } 
} 

원하는 경우 전체 코드를 게시 할 수 있습니다. 미리 감사드립니다 :)

Answer 1

여기서 복잡성은 프로그램이 내부 루프의 작업을 실행하는 횟수를 조사하여 측정됩니다.

Condition이 실행될 때마다 내부 루프는 x 번 실행됩니다. 따라서 내부 루프 복잡성은 O (x)입니다.

n 번까지 실행할 수 있습니다. 이로 인해 최악의 경우 O (x.n)의 복잡성이 제공됩니다.

Condition에 대한 추가 지식이 있으면보다 정확한 분석을 얻을 수 있습니다. 예를 들어 평균 복잡도을 계산할 수 있습니다.

예를 들어, Condition을 !(i & (i-1))이라고합시다. 사실i이 0 또는 2의 거듭 제곱 인 경우에만 루프가 실행됩니다.이 경우 루프는 정확하게 E(ln2(n)) + 2 번 실행됩니다 (E(.)은 정수 부분 기능 임). 결국 전체적인 복잡성 은이됨을 알게 됨 O (x.ln (n))