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

前言

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

在这里插入图片描述

算法复杂度（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 = 0for 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) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelse if arr[mid] < target:left = mid + 1else:right = mid - 1return -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 = 0for 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 1else: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) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1