시간 복잡성 설명

Question

사람이 알고리즘의 시간 복잡도를 찾는 방법을 설명시겠습니까 나는 그것의 O 때문에 이진 분할의 (logN), 그러나이 확실하지

int findRotationCount(int a[], int sizeOfArray) //O(logN) 
    { 
     int start = 0; 
     int endValue = sizeOfArray -1; 

     while(start<endValue) 
     { 
      if(a[start] < a[endValue]) 
       return endValue+1; 
      else 
      { 
       int mid = (start+endValue)/2; 

       if(a[start]<=a[mid] && a[mid+1]<=a[endValue]) 
        return mid+1; 
       else if(a[start]<=a[mid]) 
        start = mid+1; 
       else 
        endValue = mid; 
      } 
     } 
     return -1; 
    } 

감사 메신저 생각!

Answer 1

맞습니다. while의 각 루프는 start에서 endValue까지의 크기를 (대략) 절반으로 줄이므로 O(log n)입니다. 예를 들어 다음과 같은 분석을 찾습니다. 이진 검색은 더 자세한 정보가 필요한 경우 비슷한 구조로되어 있습니다.