【数据结构】复杂度的重要性—–决定程序运行的效率

前言

在我们写算法的时候，常常会需要考虑一个问题：这个算法好不好？而这个“好”实际上就取决于是算法的复杂度。

算法复杂度（Algorithmic Complexity）是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。

我们知道，同一个问题可以使用不同的算法来解决，而这里的不同一般来说也是可以从复杂度来看出的，当然，也不排除有相同复杂度但不同写法的算法，这里只作参考。

一个算法的好坏影响到了很多实际性的问题，在程序中效率是极其重要的，一个算法的评价主要从时间复杂度和空间复杂度来考虑。

在介绍这两个复杂度之前，我们需要了解一个概念：复杂度并不是具体的数值或者是大小表示，它实际上是一个量级的概念。

比如O(n)和O(n+1)。很明显，它们是同一个量级，只差了1，那么它们实际上可以写成同一个，也就是O(n)，甚至像O(2n)，它和上面两者也是同一个量级；但是，像O(n)和O(n^2)，这俩实际上并不属于同一个量级。它们之间隔了一个次方，那么就有可能存在大小的很大差距，所以这两个复杂度是两个不同的个体。

接下来对这两个复杂度进行具体介绍。

时间复杂度

基本定义和理解

时间复杂度衡量的是算法运行时间随输入规模的增长情况。

对于算法的运行时间，在实际中，由于每台计算机的硬件和软件环境的不同，往往不能精确计算执行所需时间。所以我们在讨论时间复杂度的时候，仅仅从理论角度，也就是视作计算机的环境不变，来进行讨论。

影响算法时间代价的具体有两个方面：问题规模和语句频度。

A.问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。

B.语句频度是一条语句的重复执行次数。一般来说，这个次数会用一个函数来表示，而这个函数代表着算法执行时间的增长率，算法执行时间的增长率称作渐进时间复杂度，也就简称为时间复杂度。

时间复杂度通常使用O(n)来表示，算法的复杂度存在最好、最坏等情况，那么在这里我们取算法的最坏运行情况作为O(n)。

在我们进行时间复杂度的解答时，实际上不需要这么复杂的解释。我们可以将其总结为一句话：

只分析算法中最耗时的操作。

由于我们考虑的是算法的最坏运行情况，并且是以量级来计算，那么我们实际上只需要分析算法中最耗时的操作即可。

分析步骤

1.确定输入规模 (n)：输入规模通常是算法中主要变量的数量，例如数组的长度。

2.识别基本操作：确定算法中最耗时的操作，其他比较繁琐、或者特殊的语句忽视。

3.分析每部分的操作次数：计算基本操作在不同结构中的次数，例如循环、递归。

4.累加所有部分的操作次数：将各部分的操作次数加起来，得到总操作次数。

5.用大O符号表示：忽略常数和低阶项，提取时间复杂度的主要部分。这里的目的实际上就是统一量级。

使用这样的步骤，我们就可以较好地解决时间复杂度的分析了。

举例

示例1：简单循环

def sum_array(arr):
    total = 0
    for i in range(len(arr)):
        total += arr[i]
    return total

步骤1：确定输入规模

输入是数组 arr，其长度为 n。

步骤2：识别基本操作

基本操作是加法 total += arr[i]。

步骤3：分析每部分的操作次数

• total = 0：1 次
• for i in range(len(arr))：循环执行 n 次
• total += arr[i]：循环体内执行 n 次

步骤4：累加所有部分的操作次数

总操作次数为 1+n+n=1+2n1 + n + n = 1 + 2n1+n+n=1+2n。

步骤5：用大O符号表示

忽略常数项和系数，时间复杂度为 O(n)。

示例2：嵌套循环

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

步骤1：确定输入规模

输入是数组 arr，其长度为 n。

步骤2：识别基本操作

基本操作是比较和交换 if arr[j] > arr[j+1] 和 arr[j], arr[j+1] = arr[j+1], arr[j]。

步骤3：分析每部分的操作次数

步骤4：累加所有部分的操作次数

分析这里的操作次数，我们可以使用更为简单的方法，请注意，这里的for循环中还嵌套了一个for循环，那么我们可以理解为：在进行大循环的时候，也会进行一次小循环，而小循环中的语句会进行n次，那么就是O(n)；而大循环会进行n次小循环，那么总的时间复杂度就是O(n*n)也就是O(n^2)。

注意：遇见嵌套类的题目，我们都这样计算：嵌套中有几个循环，就是n的几次方。

步骤5：用大O符号表示

忽略常数项和系数，时间复杂度为 O(n^2)。

示例3：二分查找

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        else if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

步骤1：确定输入规模

输入是数组 arr，其长度为 n。

步骤2：识别基本操作

基本操作是比较 arr[mid] == target。

步骤3：分析每部分的操作次数

• left, right = 0, len(arr) - 1：1 次
• while left <= right：循环次数由 left 和 right 的变化决定，每次循环减半，最多执行log2(n)次。

步骤4：累加所有部分的操作次数

总操作次数为 1+log2(n)

步骤5：用大O符号表示

忽略常数项和低阶项，时间复杂度为 O(log n)。

经过以上的介绍和举例，相信各位已经能够游刃有余地解决时间复杂度的问题了。

空间复杂度

基本定义和理解

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。当我们需要区别算法时，我们应该看到的是每个算法的不同处，由于输入的初始数据所占的存储空间是已经确定的，那么在计算空间复杂度时，我们往往只分析执行过程中所需要额外的存储空间大小。

分析步骤

1.确定输入规模 (n)：输入规模通常是算法中主要变量的数量，例如数组的长度。

2.识别存储需求：确定算法中每个变量和数据结构所需的存储空间。

3.分析每部分的存储空间需求：计算不同部分占用的空间，如局部变量、数组、递归调用栈等。

4.累加所有部分的存储空间需求：将各部分的存储空间加起来，得到总的空间需求。

5.用大O符号表示：忽略常数和低阶项，提取空间复杂度的主要部分。

举例

示例1：简单循环

def sum_array(arr):
    total = 0
    for i in range(len(arr)):
        total += arr[i]
    return total

步骤1：确定输入规模

输入是数组 arr，其长度为 n。

步骤2：识别存储需求

• arr：长度为 n，空间需求为 O(n)
• total：一个整数，空间需求为 O(1)
• i：一个整数，空间需求为 O(1)

步骤3：分析每部分的存储空间需求

• arr：O(n)
• total：O(1)
• i：O(1)

步骤4：累加所有部分的存储空间需求

总空间需求为 O(n)+O(1)+O(1)=O(n)。

步骤5：用大O符号表示

忽略常数项和低阶项，空间复杂度为 O(n)。

示例2：递归函数

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

步骤1：确定输入规模

输入是整数 n。

步骤2：识别存储需求

• 递归调用栈：每次递归调用会占用栈空间。

步骤3：分析每部分的存储空间需求

• 每次递归调用占用 O(1) 空间，最多递归调用 n 次。

步骤4：累加所有部分的存储空间需求

总空间需求为 O(1)∗n=O(n)。

步骤5：用大O符号表示

忽略常数项和低阶项，空间复杂度为 O(n)。

示例3：使用辅助数组

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

步骤1：确定输入规模

输入是数组 arr，其长度为 n。

步骤2：识别存储需求

• arr：长度为 n，空间需求为 O(n)
• 辅助数组 L 和 R：总长度为 n，空间需求为 O(n)

步骤3：分析每部分的存储空间需求

• arr：O(n)
• 辅助数组 L 和 R：O(n)
• 局部变量 i, j, k, mid：O(1)

步骤4：累加所有部分的存储空间需求

总空间需求为 O(n)+O(n)+O(1)=2O(n)+O(1)=O(n)。

步骤5：用大O符号表示

忽略常数项和低阶项，空间复杂度为 O(n)。

注意：在空间复杂度的计算中，大部分都是O(n)和O(1)，这两个复杂度是最为常见的。

如何理解和应用复杂度分析

理解复杂度分析的核心是**能够评估算法在最坏、最好和平均情况下的性能。**这有助于我们在开发过程中选择最合适的算法和数据结构以确保程序的高效运行。

算法的高效性往往在算法指标中占据较高位置，所以只要我们使得复杂度越小，高效性越高，那么算法也就会越好。

的存储空间需求**

总空间需求为 O(n)+O(n)+O(1)=2O(n)+O(1)=O(n)。

步骤5：用大O符号表示

忽略常数项和低阶项，空间复杂度为 O(n)。

注意：在空间复杂度的计算中，大部分都是O(n)和O(1)，这两个复杂度是最为常见的。

如何理解和应用复杂度分析

理解复杂度分析的核心是**能够评估算法在最坏、最好和平均情况下的性能。**这有助于我们在开发过程中选择最合适的算法和数据结构以确保程序的高效运行。

算法的高效性往往在算法指标中占据较高位置，所以只要我们使得复杂度越小，高效性越高，那么算法也就会越好。