O(log n)型別的演算法

假設我們有一個大小為 n 的問題。現在，對於我們的演算法的每一步（我們需要編寫），我們的原始問題變成其先前大小的一半（n / 2）。

所以在每一步，我們的問題都變成了一半。

當問題空間減少（即完全解決）時，在退出檢查條件後不能再進一步減小（n 變為等於 1）。

1. 讓我們說第 k 步或操作次數：

   problem-size = 1

2. 但我們知道在第 k 步，我們的問題規模應該是：

   problem-size = n / 2 k

3. 從 1 和 2：

   n / 2 k = 1 或

   n = 2 k

4. 記錄兩側

   log e n = k log e 2

   要麼

   k = log e n / log e 2

5. 使用公式 log x m / log x n = log n m

   k = log 2 n

   或者只是 k = log n

現在我們知道我們的演算法最多可以執行 log n，因此時間複雜度為
O（log n）

程式碼中支援上述文字的一個非常簡單的示例是：

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

所以現在如果有人問你，如果 n 是 256，那麼迴圈的步數（或者將其問題大小減少到一半的任何其他演算法）將會執行，你可以很容易地計算出來。

k = log 2 256

k = log 2 2 8 （=> log a a = 1）

k = 8

類似情況的另一個非常好的例子是二進位制搜尋演算法。

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}