时间复杂度是什么？

• 一个函数，用大 O 表示，比如O(1)、O(n)、O(logN)...
• 比较的是操作数（运行一次，代码执行了多少次），他指出了算法运行时间的增速
  O(n) ：O就是大O，括号里的就是操作数

上面图中我们可以重点关注1、log2n、n、n²

O(1)复杂度：

let i = 0;
i += 1;

原因：上面的代码每次只会执行一次

O(n)复杂度：

for (let i = 0; i < n; i++) {
   console.log(i);
}

原因上面的代码要遍历 n 次

O(1) + O(n) = O(n)

let i = 0;
i += 1;
for (let i = 0; i < n; i++) {
   console.log(i);
}

原因：两个时间复杂度先后排列我们就把他们相加，取那个增长趋势最快的，也就是 O(n)

O(n) * O(n) = O(n²)

for (let i = 0; i < n; i++) {
   for (let j = 0; j < n; j++) {
      console.log(i, j)
    }
}

相乘按照正常的乘法来计算，相加取增长趋势最快的

O(logN)

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

原因：只要是与 2的多少次方等于n有关的，都是 logN 因为 logN 本身就是2 的多少次方等于 n，上面每次循环都会乘以2，也就是 logN

推导原则

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

1). 场景1 T(n) = 3n， 最高阶项为3n，省去系数3，则转化的时间复杂度 为：T(n)=O(n)

2). 场景2 T(n) = 5logn， 最高阶项为5logn，省去系数5，则转化的时间复杂度为：T(n)
=O(logn)。

3). 场景3 T(n) = 2， 只有常数量级，则转化的时间复杂度为：T(n) =O(1)。

4). 场景4 T(n) = 0.5n2+ 0.5n， 最高阶项为0.5n2，省去系数0.5，则转化的时间复杂度为：T(n) =O(n2)。

O(1)<O(logn)<O(n)<O(n2)