时间复杂度和空间复杂度

简述

• 时间复杂度: 跟消耗时间相关
• 空间复杂度: 跟消耗多少内存相关

时间复杂度

简言而之: 参数n, 会导致代码执行多少次的关系公式

常用的时间复杂度有

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

常数阶O(1)

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

这里因为没有循环结构 所以无论n怎么变化, 都是只执行一次

线性阶O(n)

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

随着n的变化, 代码会执行n次

对数阶O(logN)

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

这里因为i会*2, 所以n和代码执行次数的公式是O(logn)

线性对数阶O(nlogN)

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

空间复杂度

待补充