1.2.1 算法的时间复杂度与大O表示法

算法的时间复杂度通常使用符号O表示：T(n)=O(f(n))，其中n表示问题的规模。O表示算法的执行时间与问题规模n之间的一种增长关系。下面通过实例来讲解什么是大O表示法。

1.二分查找

查找是计算机中的常见操作，下面介绍一种用来解决查找问题的算法：二分查找。二分查找的功能是在一个数学序列中查找数学，如果成功，则返回这个数的位置；如果失败，则返回空。

思考：假设现在有人在纸上写一个介于1和100之间的整数，请尝试用最少的次数猜出这个数。在你每次猜测之后，会告诉你是否正确，如果错了，会提示你大了还是小了。

方法1：假设你采用的策略是从第一个数开始猜，每次加1，过程如表1.2所示。

上述这种查找叫作简单查找，就是从第一个数开始，以此往后不断比较，直到找到该数为止。假设写在纸上的数是36，那么需要猜36次。最坏情况下，纸上的数是100，这就需要查找100次，显然对于这个问题来说，这不是一种合适的算法。

方法2：从最中间的数开始猜，猜的第一个数是50，而36<50，因而会提示你大了。由此你知道了这个数应该在50的前面，下一次查找的范围就是1～49了。再从中间的数25开始猜，而36>25，因而会提示你小了。这时候，你已经知道这个数应当在26和49之间，再从中间的数37开始猜，如此反复，直至找到36为止。猜数过程如表1.3所示。

上述这种查找叫作二分查找，就是从中间的数开始，每次将待查找空间缩小一半，不管纸上写的是什么数字，在7次之内都能够猜到，显然比简单查找算法更优。对于n个数，二分查找需要查找log₂n次。

用简单查找算法在16个数中查找数字时，最多需要查找16次，如表1.4所示。用二分查找算法在16个数中查找数字时，最多需要查找log₂16=log₂24=4次。当n=100时，最多需要查找log₂n=log₂100次，100介于64和128之间，log₂100介于log₂26和log₂27之间，取上限，最多需要查找7次。需要注意的是，使用二分查找算法的前提是数字是有序的。

简单查找算法可如下设计。

---

int Search(int a[ ], int n, int k)
{ 
      int i=0; 
      while(i < n && a[i]!=key) 
          i++; 
      if(a[i]==k) 
          return i; 
      else  
          return -1; 
 } 

---

二分查找算法可如下设计。

---

int BiSearch(int a[ ], int n, int k)
{         
       int low=0;                 //low是当前查找区间的上界，初始值为0 
       high=n - 1;                //high是当前查找区间的下界，初始值为n−1 
       int mid; 
       while(low <=high)
         { 
              mid=(low+high)/2; //确定查找区间的中心下标 
              if(k==a[mid]) 
  
                  return mid;         //查找成功，返回当前元素的下标 
              else if(k<a[mid]) 
                       high=mid - 1;//如果k小于a[mid]，将查找区间缩小至前半区 
                       else low=mid+1;//如果k大于a[mid]，将查找区间缩小至后半区 
          } 
       return -1;                     //查找失败，返回−1 
}       

---

2.大O表示法的定义

下面从算法执行时间的角度分析简单查找与二分查找两种查找算法。相对于简单查找来说，二分查找究竟节省了多少时间呢？如表1.5所示，当n的规模越来越大时，简单查找需要的次数增加得非常快，当n=100 000 000时，二分查找只需要27次，执行时间远远短于简单查找，这是为什么呢？原因是二分查找和简单查找的运行时间的增速不同。随着问题规模n的增加，二分查找增加的时间并不多，而简单查找增加的时间却很多。因此，随着问题规模不断增大，二分查找的速度比简单查找快得多。算法分析就是找出运行时间如何随问题规模的增加而增加，这也正是大O表示法的用武之地。

大O表示法：T(n)=O[f(n)]，其中n表示问题的规模。使用大O表示法，简单查找的运行时间就是O(n)，二分查找的运行时间就是O(log₂n)。综上所述，我们得出结论，算法的时间复杂度不是指算法运行一次需要多长时间，而是指随着问题规模的增加，运行时间将以什么样的速度增加。O(log n)比O(n)快，需要查找的元素区间越多，前者比后者快得越多。

3.推导大O阶

下面将介绍如何分析算法的时间复杂度。在算法分析中，我们将语句总的执行次数记为T(n)，进而分析T(n)随n的变化情况，从而确定T(n)的数量级，即推导大O阶。具体分为以下4个步骤。

（1）分析问题的规模n，找出算法中的基本语句，计算出T(n)。

（2）用常数1取代T(n)中的加法常数项。

（3）在T(n)中，只保留其中的最高阶项。

（4）如果最高阶项存在且不是1，就去掉它的系数，所得结果便是大O阶。

算法中的基本语句是指算法中执行次数最多的语句，通常是最内层循环的循环体；如果算法中包含并列的循环，就将并列循环的时间复杂度相加。算法分析需要计算基本语句执行次数的数量级，即只要保证基本语句中执行次数的函数的最高次幂正确即可，因为随着问题规模的变大，常数项对T(n)增速几乎没有什么影响，所以可以不予考虑。另外随着问题规模的变大，最高阶以外的其他低次幂对T(n)增速的影响是远远低于最高阶的，可以忽略所有低次幂和最高次幂的系数，这样能够简化算法分析，并且使注意力集中在最重要的增长率上。

如表1.6所示，假设求得T(n)=3n2+n+2，分别算出n+2、3n2、n2的值并进行比较，可以看出经上述方法推导出的大O阶，从而较好地反映出随着问题规模的增加T(n)的增长速度。