grisse / blog Goto Github PK

算法的执行效率，粗略地讲，就是算法代码执行的时间。如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

大O复杂度表示法

其中，T(n)表示代码执行的时间；n表示数据规模的大小；f(n)表示每行代码执行的次数总和。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

如何分析一段代码的时间复杂度？分享三个比较实用的时间复杂度分析方法。

1.只关注循环执行次数最多的一段代码

大O时间复杂度法只是表示一种变化趋势，所以我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我 们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，就是整段要分析代码 的时间复杂度。

这里有段非常简单的代码，求1,2,3…n的累加和。我们就以这段代码为例来说明。

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

其中第2、3行代码都是常量级的执行时间，与n的大小无关，所以对于时间复杂度并没有影响。循环执行次数最多的是第4、5行代码，所以要重点分析这段代码。这两行代码被执行了n次，所以总的时间复杂度就是O(n)。

2.加法法则：总复杂度等于量级最大的那段代码的复杂度

这里还有一段代码。

int cal(int n){
    int sum_1 = 0;
    int p = 1;
    for (; p<100; ++p){
        sum_1 += p;
    }

    int sum_2 = 0;
    int q = 1;
    for (; q<n; ++q){
        sum_2 += q;
    }

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

    return sum_1 + sum_2 + sum_3;
}

这个代码分为三部分，分别是求sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的时间复杂度。

第一段代码循环执行了100次，是一个常量的执行时间，跟n的规模无关，所以时间复杂度是O(1)。

第二段和第三段代码的时间复杂度分别是O(n)和O(n²)。

综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为O(n²)。即：总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：

如果T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) = O(max(f(n),g(n))).

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

有了加法法则，这里还有一个乘法法则：

如果T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

也就是说，假设T1(n) = O(n)，T2(n) = O(n²)，则T1(n) * T2(n) = O(n³)。落实到具体的代码上，我们可以把乘法法则看成是嵌套循环，看下面的例子。

int cal(int n) {
    int ret = 0;
    int i = 1;
    for (; i<n; ++i){
        ret = ret + f(i);
    }
}

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

我们单独看cal()函数，假设f()只是一个普通操作，，那第4-6行的时间复杂度就是T1(n)=O(n)。但f()函数本身不是一个简单的操作，它的时间复杂度是 T2(n)=O(n)，所以，整个cal()函数的时间复杂度就是 T(n) = T1(n) * T2(n) = O(n*n) = O(n²)。

几种常见时间复杂度实例分析

1. O(1)

O(1)是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有3行，它的时间复杂度也是O(1),而不是O(3)。

int i = 8;
int j = 6;
int sum = i + j;

只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。

2. O(logn)、O(nlogn)

O(logn)

看下面的例子。

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

根据前面说的时间复杂度分析方法，我们只要计算出第3行代码执行的次数，就能知道整段代码的时间复杂度。

从代码中可以看出，变量i的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。

实际上，变量i的取值就是一个等比数列。如果把它一个一个列出来，就应该是这个样子的：

2⁰, 2¹, 2²···2^k··· 2^x = n

x的值就是这行代码执行的次数。通过2^x=n求解可得x=log₂n,所以这段代码的时间复杂度就是O(log₂n)。

实际上，我们可以把所有对数阶的时间复杂度都记为O(logn)。

这是因为对数之间是可以互相转换的，log₃n就等于log₃2 * log₂n，所以O(log₃n) = O(C * log₂n)，其中C=log₃2是一个常量。基于我们前面的一个理论：在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))。所以，O(log₂n) 就等于O(log₃n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”， 统一表示为O(logn)。

O(nlogn)

根据前面说的乘法法则，如果一段代码的时间复杂度是O(logn)，循环执行n遍，时间复杂度就是O(nlogn)了。归并排序、快速排序的时间复杂度都是O(nlogn)。

3. O(m+n)、O(m*n)

看下面这段代码。

int cal(int m,int n) {
    int sum_1 = 0;
    int i = 1;
    for (; i<m; ++i) {
        sum_1 += i;
    }

    int sum_2 = 0;
    int j = 1;
    for (; j <n; ++j) {
        sum_2 += j;
    }
    return sum_1 + sum_2;
}

从代码可以看出，m和n是表示两个数据规模。代码的复杂度由两个数据的规模来决定，所以就不能简单的利用加法法则，省略其中一个。所以，上面代码的时间复杂度就是O(m+n)。

针对这种情况，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

空间复杂度全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

看下面的代码例子。

void print(int n){
    int i = 0;
    int[] a = new int[n];
    for (; i<n; ++i) {
        a[i] = i * i;
    }

    for(i = n-1; i >= 0; --i){
        print out a[i];
    }
}

第2行代码中申请了一个空间存储变量i，但是它是常量阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。

常见的空间复杂度就是O(1)、O(n)、O(n²)，像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。

小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)。

地址是啥？？