complexity.md

时间与空间复杂度知识点

时间复杂度

算法的时间复杂度（Time complexity）是一个函数。表示一个趋势，即是输入值大小趋近无穷情况下，不考虑这个函数的低阶项和首项系数，它的渐进时间与某指数方程接近 例如：函数f(x) => 5n^3 + 3n，它的时间复杂度就是O(n^3)，即是程序运行时间会与n^3指数接近 复杂度通常使用大O符号表示法 最坏情况复杂度通常使用T表示

常见时间复杂度列表

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• k次方阶O(n^k)
• 指数阶(2^n)
• 阶乘(n!)

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1) 它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

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

线性阶O(n)

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

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

对数阶O(logN)

如果在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了，假设循环x次之后，i 就大于 n 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n， 那么 x = log2^n

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

线性对数阶O(nlogN)

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

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

k次方阶O(n^k)

如果把 O(n) 的代码再嵌套循环k遍，它的时间复杂度就是 O(n^k) 了, 下面例子是一个2次方阶，嵌套了2次循环

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

指数阶O(2^n)

无例子

阶乘O(n!)

无例子

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。记做S(n)=O(f(n))，其中n为问题的规模(或大小)。通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为0(1)