算法的时间和空间复杂度

罗珍玲

学习内容：
一、时间复杂度
用「 大O符号表示法 」，即 T(n) = O(f(n))
举个例子

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

根据上面的例子，假设每行代码的执行时间都是 1颗粒时间 ，那么第一行耗时是1个颗粒时间，第三、四行的执行时间是 n个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ，即 (1+2n)个颗粒时间，即： T(n) = (1+2n)*颗粒时间，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中，如果n无限大的时候，T(n) = time(1+2n)中的常量1就没有意义了，倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了，即执行次数的最大数量级。

常见的时间复杂度量级有：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

常见时间复杂度的例子

1. 常数阶O(1)

无循环，最大数量级为1，时间复杂度为O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
2.  线性阶O(n)

一层循环，最大数量级为n，时间复杂度为O(n)

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
3. 对数阶O(logn)

一层循环，最大数量级为logn，时间复杂度为O(logn)

循环1次，i=2；循环2次，i=2^2；循环3次，i=2^3；...；循环x次，i=2^x=n，x=log2^n，所以循环次数的最大数量级为logn

int i = 1;
while(i<n)
{
    i = i * 2;
}
4. 线性对数阶O(nlogN)

两层循环，最大数量级为nlogn，时间复杂度为O(nlogn)

时间复杂度为O(logn)的循环外再加一层n循环，即n*O(logn)

for(m=1; m<=n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}
5. 平方阶O(n²) / n*m阶O(n*m)

两层循环，最大数量级为n^2，时间复杂度为O(n^2)

嵌套两层n循环

for(x=1; x<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
两层循环，最大数量级为n*m，时间复杂度为O(n*m)

嵌套两层循环，外层循环m次，内层循环n次

for(x=1; x<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
立方阶O(n³)、K次方阶O(n^k)类似

二、空间复杂度
定义=是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，用 S(n) 来定义。

常见的空间复杂度：O(1)、O(n)、O(n²)

举个

1. 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
2. 空间复杂度 O(n)

第一行的数组占用的大小为n，代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}