常碰到的时间复杂度

其中指数阶和阶乘阶都属于十分低效的复杂度量级，应该尽量避免。

时间复杂度.png

下面这段代码的时间复杂度为log(n)

//这段代码的时间负责度就是log(n)
 i=1;
 while (i <= n)  {
   i = i * 2;
 }

最好与最坏情况下的时间复杂度

• 最好时间复杂度
• 最坏时间复杂度
• 平均时间复杂度

最好时间复杂度和最坏时间复杂度都很好理解，那么什么是平均复杂度呢？
我们先看下面代码：

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

• 最好时间复杂度为O(1)，最坏时间复杂度为O(N)；

• 平均时间复杂度计算如下：
  要查找的变量 x 在数组中的位置，有 n+1 种情况（n种找到、1种未找到），这n+1种情况分别查找1、2、3....n-1、n、n次，那么平均时间复杂度如下：

  
  
  计算过程.png

如果假设找到与没找到的概率都为1/2，那么加权平均时间复杂度（期望时间复杂度）为：

加权平均时间复杂度计算.png

什么是均摊时间复杂度呢？