時間複雜度說明

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)。尋找例如二進制搜索，如果您需要更多詳細信息，它具有相似的結構。