时间空间复杂度

如何衡量一个算法的好坏: 一是跑的快不快，二是消耗多少空间。把这两个维度合起来就是时间复杂度和空间复杂度。

算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间分析的，即时间复杂度和空间复杂度。 

时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量一个算法运行时所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很在乎，但是经过计算机行业的飞速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要特别关注一个算法的空间复杂度。

时间复杂度

大O表示法 算法的渐进时间复杂度

T(n) = O(f(n))         f(n)代表的是代码执行的次数, O()是表示正比例关系

推导大O阶方法:

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中, 只保留最高阶项
3. 如果最高阶项存在且不为1, 则去除与这个项目相乘的常数(系数). 得到的结果就是大O阶

常用的时间复杂度量级

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

图中X轴可以理解为是输入的问题的量级, Y轴是时间的复杂度.

可以看到(n!), (2^n), (n^2) 随着X的增长, 它的时间复杂度增长趋势是指数级增长的. 如果你写的一个算法,时间复杂度是指数级增长的话, 那说明这个算法是非常非常烂的.

简单介绍一些其中比较常用的量级

O(1)

可以看到这段代算法的复杂度不会随着任何一个变量的增大而变的更复杂, 就算这段代码重复一千行一万行, 它的时间复杂度还是O(1), 是一个常量

int x = 0;
int y = 1;
int temp = x;
x = y;
y = temp;

O(n)

这个算法的时间复杂度取决于n的大小, n越大, 算法复杂度越高

for(int i = 0; i < n; i++)
{
    x++;
}

O(logN)

这段代码的 i 会随着循环次数的增加, 每次被乘2, 会越来越接近于 n . 

那么要循环多少次, 这个 i , 才会大于等于 n 呢?

        2 ^ K = n (K就是循环的次数)

        k = logN (K就是算法的复杂度)

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

O(nlogN)

这个很好理解,就是在logN的基础上加一层 n 层的循环次数, 就是n的循环次数乘logN

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

O(n^2)

就是外边一层循环, 里边也有一层循环(n * n)

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

同样的, n^3就是三层循环, n^k就是k层循环

其他复杂度指标

除了Big O, 还有其他复杂度指标

• O(Big O)最差情况 (算法分析最常用指标)
• Ω(Big Omega)最好情况
• Θ(Big theta)一个算法的区间

空间复杂度

空间复杂度是对一个算法在运行过程中临时额外占用存储空间大小的量度

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数

空间复杂度计算规则基本跟时间复杂度类似， 也使用大O渐进表示法

注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定

常用的空间复杂度

• O(1)
• O(n)
• O(n^2)

O(1)

这段代码需要的空间是一个常数量, x与y的数值再大也不会影响空间分配, 所以就是O(1)的空间复杂度

int x = 0;
int y = 0;
x++;
y++;

O(n)

在这段代码中, 这个数组的长度是n, 随着n的变化, 数组内的元素也会产生变化. 所以这个算法复杂度取决于newArray数组的长度, 随着n越大, 算法复杂度就越高, 需要分配的空间也越多

int newArray[n];
for(int i = 0; i < n; i++)
{
    newArray[i] = i;
}

O(n^2)

根据二维数组长度为n分配的内存, 空间复杂度是n^2

时间空间复杂度 = 时间和空间增长的趋势