算法复杂度分析看这一篇就够了

2023年也慢慢的步入了年末，光阴易逝，前段时间在学习算法的时候谈到了复杂度，所以今天就来总结一下

算法的复杂度是衡量算法执行效率的度量标准。它描述了随着输入规模的增加，算法所需执行的基本操作的数量或运行时间的增长程度。一般来说，算法的复杂度可以分为时间复杂度和空间复杂度。

时间复杂度衡量的是执行算法所需的时间，通常以大O符号（O）来表示。例如，O(1)表示常数时间复杂度，即算法的执行时间与输入规模无关；O(n)表示线性时间复杂度，算法的执行时间与输入规模呈线性关系；O(n^2)表示平方时间复杂度，算法的执行时间与输入规模的平方成正比，等等。

空间复杂度衡量的是算法在执行过程中所需的额外空间，通常也使用大O符号进行表示。空间复杂度可以用于评估算法在内存消耗方面的效率。与时间复杂度类似，O(1)表示常数空间复杂度，O(n)表示线性空间复杂度，O(n^2)表示平方空间复杂度，等等。

总的来说，算法的复杂度帮助我们评估算法的效率和可扩展性，从而在设计和选择算法时做出更明智的决策。

学好算法需要具备那些点

学习算法需要具备以下几个品质：

• 好奇心：对于算法和问题的好奇心是非常重要的。好奇心会驱使你主动去了解和探索各种不同类型的算法，以及它们在解决问题上的应用。

• 坚持与耐心：学习算法是一个需要持续努力和坚持的过程。有时算法可能会很复杂或难以理解，但通过持之以恒的学习和实践，你将逐渐掌握它们。

• 数学基础：虽然不是所有的算法都需要深厚的数学知识，但良好的数学基础可以帮助你更好地理解和分析算法的原理和表现。

• 逻辑思维能力：算法与逻辑密切相关，因此具备良好的逻辑思维能力可以帮助你更好地理解和设计算法。

• 编程能力：学习算法通常需要使用编程语言来实现和测试。因此，具备一定的编程能力，熟悉常见的编程语言和算法实现方式是必要的。

• 分析和解决问题的能力：学习算法的目的是为了解决实际问题。具备良好的问题分析和解决能力可以帮助你选择适当的算法，并应用它们来解决实际问题。

• 团队合作能力：在现实世界中，算法通常是由团队合作开发和优化的。具备良好的团队合作能力可以帮助你更好地与他人交流和协作，共同完成算法实现和优化的任务。

学习算法需要持续地学习、实践和思考，同时具备好奇心、耐心、数学基础、逻辑思维能力、编程能力、问题解决能力和团队合作能力。通过培养这些品质，你将能够更好地理解和应用不同类型的算法。

1.1 算法复杂度分析

1.1.1 概念

1. 数据结构是指一组数据的存储结构
2. 算法就是操作数据的方法

举个例子：

比如，你要搬家，有一堆货物，这个时候你可以选择使用小桥车拉走货物，你可以选择小货车拉走货物。其实现在你选择哪辆车装载货物就相当于选择了哪种数据结构。

你选择小货车拉走货物，但是货物依然很多，你这个时候需要规整一下，难看怎么着更能节省空间，更能节省效率，这个动作就是算法了

清楚了这些概念之后，如果只是单独讲数据结构和算法是不合适的，它们两个是相辅相成的。

1.1.2 算法复杂度

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。

复杂度描述的是算法执行时间或占用内存空间随数据规模的增长关系。

举例：

有200人需要从成都到北京，可以选择很多交通工具，每个交通工具的载客量和时间都不相同

• 大型载人客车，50人每车，需要4辆车，时间大概为30小时
• 普通火车，载客量超大，满足200人的需求，时间大概为20小时
• 高铁，载客量超大，满足200人的需求，时间大概为9小时
• 飞机，载客量适中，满足200人的需求，时间大概为3小时

算法的执行效率，粗略地讲，就是算法代码执行的时间，那如何在不直接运行代码的前提下粗略的计算执行时间呢？

分析以下代码

/**
  * 求1~n的累加和
  * @param n
  * @return
  */
public static int sum(int n){
    int sum = 0;
    for (int i = 1; i < n; ++i) {
        sum  = sum + i;
    }
    return sum;
}

假设每行代码执行时间都一样为：timer

此代码的执行时间为：(3n+3) timer

总结：所有代码的执行时间T(n)与代码的执行次数成正比。

按照该思路我们接着看下面一段代码

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

同理，此代码的执行时间为： (3 n^2 + 3n + 3) * timer

因此有一个重要结论：代码的执行时间T(n)与总的执行次数相关 ，我们可以把这个规律总结成一个公式。

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

T(n)表示代码的执行时间，n表示数据规模的大小，f(n)表示了代码执行的总次数，它是一个公式因此用f(n)表示，O表示了代码执行时间与f(n)成正比

1.1.3 大O复杂度表示法

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

当n很大时，公式中的低阶，常量，系数三部分并不左右其增长趋势，因此可以忽略，我们只需要记录一个最大的量级就可以了，因此如果用大O表示刚刚的时间复杂度可以记录为

第一个例子中的T(n)=O(3n+3) -----> T(n)=O(n)

第二个例子中的T(n)=O(3 n^2 + 3n + 3) -------> T(n)=O(n^2)

常见的复杂度

描述	表示形式
常数	O(1)
线性	O(n)
对数	O(log n)
线性对数	O(n * log n)
平方	O(n ^2)
立方	O(n ^3)
k次方	O(n ^k)
指数	O(2 ^n)
阶乘	O(n !)

1.1.4 O(1)

public int test01(int n){
    int i=0;
    int j = 1;
    return i+j;
}

代码只有三行，它的复杂度也是O(1)，而不是O(3)

再看如下代码：

public void test02(int n){
    int i=0;
    int sum=0;
    for(;i<100;i++){
        sum = sum+i;
    }
    System.out.println(sum);
}

整个代码中因为循环次数是固定的就是100次，这样的代码复杂度我们认为也是O(1)

一句话总结：只要代码的执行时间不随着n的增大而增大，这样的代码复杂度都是O(1)

1.1.5 O(n)

这个大家已经不陌生了，就是刚才上面的两个例子

/**
 * 求1~n的累加和
 * @param n
 * @return
 */
public int sum(int n) {
    int sum = 0;
    for ( int i = 1; i <= n; i++) {
        sum = sum + i;
    }
    return sum;
}

一层for循环的时间复杂度是 O(n)

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

两层for循环的时间复杂度是 O(n^2)

1.1.6 O(log n)

对数复杂度非常的常见，但相对比较难以分析，代码：

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

分析这个代码的复杂度，我们必须要再强调一个前提：复杂度分析就是要弄清楚代码的执行次数和数据规模n之间的关系

以上代码最关键的一行是：i = i * 2，这行代码可以决定这个while循环执行代码的行数，i的值是可以无限接近n的值的。如果i 一旦大于等于了n则循环条件就不满足了。也就说达到了最大的行数。我们可以分析一下i这个值变化的过程

分析过程如下：

由此可知，代码的时间复杂度表示为O(log n)

1.1.7 O(n * log n)

分析完O( log n )，那O( n * log n )就很容易理解了，比如下列代码：

public void test05(int n){
    int i=0;
    for(;i<=n;i++){
        test04(n);
    }
}

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

1.1.8 空间复杂度

空间复杂度全称是渐进空间复杂度，表示算法占用的额外存储空间与数据规模之间的增长关系

看下面代码

public void test(int n){
    int i=0;
    int sum=0;
    for(;i<n;i++){
        sum = sum+i;
    }
    System.out.println(sum);
}

代码执行并不需要占用额外的存储空间，只需要常量级的内存空间大小，因此空间复杂度是O(1)

再来看一个其他例子：

void print(int n) {
    int i = 0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] = i * i;
    }
    for (i = n-1; i >= 0; --i) {
        System.out.println(a[i]);
    }
}

传入一个变量n，决定申请多少的int数组空间内存，此段代码的空间复杂度为O(n)

我们常见的空间复杂度就是O(1),O(n),O(n ^2)，其他像对数阶的复杂度几乎用不到，因此空间复杂度比时间复杂度分析要简单的多。