[算法基础]Big O Notation时间复杂度计算方法

首先一点就是无视任何常量

从最简单的开始

statement;

这段时间复杂度为常数1,所以O(1).

然后

for ( i = 0; i < N; i++ )
  statement;

这一段是线性的,则时间复杂度为N,所以O(N),就算运行多次,比如4次5次,5N依然看做O(N).

但是

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

这一段则是二次的,不是二次元,是二次quadratic,这一段的运行次数为N*N,所以O(N^2).

再一个例子

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

这一段是对数的Logarithmic,有点难理解吧,就是说以上的例子每次都要找到中间的部分,那么中间的部分找到后,整个size就一分为二,只用管其中的一半即可.考虑到整个list的size,我们假设这个size为X,那么以上的步骤要重复Y次才能达到X,介于每次都是取一半丢一半,那么可以说2^Y=X,因为计算机理论方面习惯吧底数为2的省略(数学里面则是底数为10的省略,略写为lg),所以其实运行次数Y=logX,也就是O(logN).

我们带几个例子来看对不对,比如我们有一个size为8的list,看看是不是需要3次就能让中间值固定下来.size为8的话,想象一个完美的例子1,2,3,4,5,6,7,8.中间值为(1+8)/2=4, target为4,然后取一半,选多的一半,则是4,5,6,7,8这边,中间值为6,再选一半,6,7,8,中间值为7,找到.以上找中间值的步骤重复了3次,刚好是我们期望中的次数.

以上例子再升级

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

就是我们通常了解的quicksort,因为多嵌套了一个iteration,所以整个运行次数为N*log(N).那么big O为O(nlog(n)).