간단한 단계를 사용하여 반복 알고리즘의 시간 복잡도를 계산하는 방법은 무엇입니까?

Question

다음 코드 조각이 있으며이 루핑 구조의 시간 복잡성을 찾기 위해 완전히 손실되었습니다. 사실 그것은 Quicksort에서 왔고이 루핑 구조는 복잡성 O (n)을 가지고 있지만 이해할 수는 없다는 것을 읽었습니다. 사실 나는 단순한 증가 또는 감소 조건 이외의 몇 가지 참 거짓 조건이 충족되는 루프 동안 루프의 복잡성을 계산하는 방법을 이해할 수 없습니다.

while (i <= j) { 
     while (array[i] < somevalue) 
       i++; 
     while (array[j] > somevalue) 
       j--; 
     if (i <= j) { 
      #do something 
       i++; 
       j--; 
     } 

    }; 

Answer 1

이 루프의 복잡성은 대략 #do something이 호출 된 횟수입니다.

최악의 경우 array[i] < somevalue이나 array[j] < somevalue도 반복 될 수 없습니다. 그런 다음 #do something을 N/2 번 (반올림 한 경우 -이 경우 중요하지 않음)이라고하며, 루프에 들어가면 i+j = N이라고 가정합니다.

우리는 위 descrease 낮은 본질적 2.

그래서, 시간 복잡도가 O(N)과 동일 O(N/2)입니다 크기의 단계를 만들고, 동시에 결합이 증가 할 때문에이 N/2입니다.

Answer 2

O(N) 가치 충족하거나 서로 교차 할 때 i+j = N 때문이다.

i과 j은 결국 (i <= j)이 거짓이되는 방식으로 만난다.

i ->        <- j 

<------------------N------------------->