复杂度分析：如何进行时间复杂度和空间复杂度分析？

如何衡量算法的优劣？

对于同一个问题，可能有很多种解决的套路，这个解决问题的套路就是算法。比如有如下一个问题，1-100的和是多少

你可以能会写出如下方案

for (int i = 1; i <= 100; i++) {
    sum += i;
}

如果你的数学基础稍微好一点，你可能就会写出如下解决方案

sum = (1 + 100) * 50;

这2个方案哪个好呢？你肯定会说第二个，因为第二个执行的时间更短。

我们一般从时间 和空间 方面衡量算法的时候复杂度

时间复杂度：执行当前算法所耗费的时间 空间复杂度：执行当前算法需要占用的内存空间

时间复杂度分析

我们如何估算代码的时间复杂度呢？

public int calSum(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; i++) {
        sum += i;
    }
    return sum;
}

以上面这段代码为例，假设每行代码的执行时间为unit_time，第2，3行的执行分别需要一个unit_time，第4，5行的执行分别需要一个unit_time，那么这段代码的执行时间为 T(n)=(2n+2)*unit_time

public int calSum(int n) {
    int sum = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; i++) {
        j = 1;
        for (; j <= n; j++) {
            sum += i * j;
        }
    }
    return sum;
}

按照上面的分析思路，这段代码的执行时间为

T(n)=(3+2n+$2n^2$)*unit_time

尽管不知道unit_time的具体值，但从上面的公式我们可以看出，所有代码的执行时间T(n)和每行代码的执行次数f(n)成正比 。我们可以把这个规律总结为如下一个公式

T(n)=O(f(n))

公式中的O表示T(n)和f(n)成正比，所以上面的2个执行时间用大O表示法为T(n)=O(2n+2)，T(n)=O($2n^2$+2n+2)。但是大O表示法并不表示具体的执行时间，只要表现出代码运行时间随数据增长的趋势即可 因此代码中的低阶，常量和系数堆增长趋势的影响比较小。我们只需要关心高阶即可，上面例子中的时间复杂度用大O表示法简化为T(n)=O(n)，T(n)=O($n^2$)

常用的时间复杂度有如下几种

常数阶O(1)

无论代码执行了多少行，只要是没有循环，递归等复杂语句，那么代码的时间复杂度就是O(1)

int a = 10;
int b = 20;
int sum = a + b;

线性阶O(n)

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

for循环里面的代码会执行n遍，它消耗的时间是随n的变化而变化的，因此用O(n)表示它的时间复杂度

对数阶O(logn)

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

由对数函数可得$2^x$=n，其中x即为代码循环的次数，x=$\log_2 n$，这段代码的时间复杂度为O($\log_2 n$)

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

同理，这段代码的时间复杂度为O($\log_3 n$)，一般情况下我们统计把对数阶的时间复杂度计为O(logn)，不管这个对数函数是以2，3，或者10位底

因为O($\log_3 n$)=O($\log_3 2$ * $\log_2 n$)，在大O表示法中系数可以忽略，进而简化为O(logn)

线性对数阶O(nlogn)

将时间复杂度为O(logn)的代码循环n遍的话，那么它的时间复杂度就是O(nlogn)

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

平方阶O($n^2$)，立方阶O($n^3$)，k次方阶O($n^k$)

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

很明显的就能看出谁见复杂度为O($N^2$)

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

当我们无法评估m和n数据规模的大小，就不能随意省略，最终的时间复杂度为O(m*n)

空间复杂度分析

空间复杂度的分析比时间复杂度的分析简单很多，常用的空间复杂度为O(1)，O(n)，O($n^2$)

int i = 1;
int j = 2;

算法需要的空间不随着某个变量值的增大而增大，则空间复杂度为O(1)

int[] array = new int[n]

算法需要的空间随某个变量值的增大而增大，则空间复杂度为O(n)