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
}