• 所有代码的执行时间与每行代码的执行次数成正比。

• 大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是代码的执行时间随着数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

一、分析时间复杂度的方法：

1. 只关注循环执行次数最多的一段代码

   
   
   image.png
   
   

   第2行的执行时间属于常量极，当数据规模趋于无穷大的时候，第2行对于复杂度并没有影响。起到主要影响作用的是第3、4行，它们的执行次数是2n，所以总的时间复杂度就是O(n)。
   （通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级）

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
   

   image.png
   
   result1 的时间复杂度是常数，对于总的时间复杂度没有影响，result2 和 result3 的时间复杂度是 O(n) 和 O()。

总的时间复杂度是多少呢？
依据总复杂度等于量级最大的那段代码的复杂度，我们可以得出总的时间复杂度为 O()

3. 乘法法则：嵌套代码的复杂度等于嵌套内代码的复杂度的乘积
   result3 的时间复杂度就是通过这种方式计算所得。

二、几种常见时间复杂度：

越高阶复杂度的算法，执行效率越低。

常量阶：O(1)
对数阶：O()
线性阶：O(n)
线性对数阶：O()
k次方阶：O()
（上面的复杂度是从低阶到高阶排序）

1.O(1)

int a = 1;
String str = "With practice getting better every day ";

2.O()

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

这段代码的执行次数取决于 i 的值，执行过程中它的值应该是 、、、... = n ，
那么执行次数 x = ，所以时间复杂度为 O()。

其实无论底数为3、4、5或者10，通常都将对数阶的时间复杂度表示为O()。

因为对数之间可以相互转换，比如 = * ，那么 O() = O( * )，又根据前面的所讲的系数部分可以忽略，所以 O() = O()。

因此我们通常将对数阶的时间复杂度表示为O()。

3. O()

for(int i=0;i<n;i++){
   j=1;
   while (j <= n)  {
     j = j * 2;
   }
}

三、最好、最坏、平均、均摊时间复杂度

示例代码：

//查找 x 在数组中的索引，如果找不到，返回 -1
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int pos = -1;
  for (i = 0; i < n; ++i) {
    if (array[i] == x) {
      pos = i;    
      break;
    }
  }
  return pos;
}

顾名思义，
①最好情况时间复杂度，就是在最理想的情况下，执行这段代码的时间复杂度。
在这里，如果数组的第一个元素正好就是要查找的变量 x ，就是最好情况，时间复杂度为 O(1)；

②最坏时间复杂度，就是在最糟糕的情况下，执行这段代码的时间复杂度。
在这里，如果数组的最后一个元素正好就是要查找的变量 x ，就是最好情况，时间复杂度为 O(n)；

③平均时间复杂度
需要从两方面考虑：

1.要查找 x 在数组中的位置，有多少种情况
2.每种情况的概率是多少

• 有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中
• 各种情况的概率：假设在数组中和不在数组中的概率都为 ，要查找的数据出现在 0~n-1 这 n 个位置的概率都为 ，那么要查找数据出现在 0~n-1 中任意位置的概率就是 。

那么平均时间复杂度的计算过程如下：
1 x + 2 x + 3 x + ... + n x + n x =

用大 O 表示法来表示，去掉系数和常数，这段代码的平均时间复杂度为 O(n)。
这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度全称应该叫加权平均时间复杂度或者期望时间复杂度。

④均摊时间复杂度

 // array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
public void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

上面的代码，实现了一个向数组中插入数据的功能。当数据满了之后，将数组中的所有数字求和，并清空数组，将得到的和值放到数组的第一个位置，然后再将新的数据插入。如果一开始数组就是空的，则直接将数据插入数组。

它的时间复杂度在数组未满的情况下是 O(1)，当数组满的时候是 O(n)。
并且有两个特点：1.大部分情况下是 O(1)，少部分情况下是 O(n)； 2.两种情况的出现是非常有规律的，O(n)、O(1)、O(1)、O(1)...... O(n)、 O(1)、O(1)、O(1).......O(n)、O(1)、O(1)、O(1)...... 循环往复。

针对这种特殊场景，引入一种更加简单的分析方法：摊还分析法，得到时间复杂度叫做均摊时间复杂度。基本上可以认为，均摊时间复杂度就是一种特殊的平均时间复杂度。

大致思路是：把耗时多的那一次均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这组连续的操作的均摊时间复杂度就是 O(1)。

参考：https://time.geekbang.org/column/article/40036