时间复杂度.md

时间复杂度

Digest

时间复杂度(time complexity), 是以数学抽象的方式用于评价一个算法在时间维度上的消耗。通常使用 O 来表示

常见的时间复杂度有

1. O(1)
2. O(logn)
3. O(n)
4. O(nlogn)
5. O($n^2$)
6. O($n^k$)
7. O($2^n$)

O(1)

常数阶

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

O(n)

线性阶

在一个 for 循环中执行 n 次

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

O(logn)

对数阶

从下面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n 也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

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

例如 二分查找 就是一个 O(logn) 算法

O(nlongn)

线性对数阶

即将复杂度 O(logn) 的代码循环 n 遍

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

O($n^2$)

平方阶

就是把 O(n) 的代码，循环 n 遍

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

例如 冒泡排序、插入排序 都是 O($n^2$) 算法

O($n^k$)

K 次方阶

就是把 O(n) 的代码，循环 $n^k$ 次

references

1. [^https://zhuanlan.zhihu.com/p/50479555]
2. [^https://programmercarl.com/%E5%89%8D%E5%BA%8F/%E5%85%B3%E4%BA%8E%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%8C%E4%BD%A0%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84%E9%83%BD%E5%9C%A8%E8%BF%99%E9%87%8C%EF%BC%81.html#%E4%BB%80%E4%B9%88%E6%98%AF%E5%A4%A7o]