Big O 备忘单：用 Python 示例进行解释

0 Shares

理解算法效率：大O分析详解

大O分析是一种用于评估和比较算法效率的强大工具。它帮助我们选择既高效又具有良好扩展性的算法。本文将作为一份大O速查表，深入解析大O符号的相关知识。

什么是大O分析？

大O分析的核心在于考察算法在输入规模增大时效率的变化。具体来说，我们关注的是，当算法处理的数据量增加时，其性能表现如何。

效率主要体现在系统资源的使用上，例如时间和内存。在大O分析中，我们主要关注以下两个问题：

当输入规模增长时，算法的内存消耗如何变化？
当输入规模增长时，算法的运行时间如何变化？

第一个问题的答案被称为“空间复杂度”，而第二个问题则对应“时间复杂度”。我们使用一种特殊的符号系统，即“大O符号”来表达这些复杂度，这将在后续部分详细介绍。

前置知识

为了更好地理解本文内容，您需要具备一定的代数基础。此外，由于本文会提供Python代码示例，了解一些Python编程知识也会有所帮助。但不必过于深入，因为您无需编写任何代码。

如何进行大O分析

本节将逐步介绍如何执行大O分析。

在进行大O复杂度分析时，务必记住算法的性能会受到输入数据结构的影响。

例如，对于排序算法而言，当列表中的数据已经按照正确顺序排列时，算法的执行速度最快，这被称为最佳情况。相反，当数据以相反的顺序排列时，算法的执行速度最慢，被称为最坏情况。

在进行大O分析时，我们通常只考虑算法在最坏情况下的表现。

空间复杂度分析

我们首先来探讨如何进行空间复杂度分析。我们需要关注的是，随着输入规模的扩大，算法所使用的额外内存如何增长。

例如，下面这个函数使用递归方式从n循环到零。它的空间复杂度与n成正比。这是因为当n增大时，调用堆栈上的函数调用数量也会相应增加，因此其空间复杂度为O(n)。

def loop_recursively(n):
    if n == -1:
        return
    else:
        print(n)
        loop_recursively(n - 1)

以下是更高效的实现方式：

def loop_normally(n):
    count = n
    while count >= 0:
        print(count)
        count =- 1

在上述代码中，我们仅创建了一个额外的变量并用它来进行循环。即使n变得非常大，我们也只会用到一个额外变量。因此，此算法的空间复杂度是恒定的，表示为O(1)。

通过对比上述两个算法的空间复杂度，我们可以得出结论：使用while循环比递归更高效。这正是大O分析的意义所在：评估算法在处理不同大小输入时的性能差异。

时间复杂度分析

进行时间复杂度分析时，我们并不关心算法执行的绝对时间，而是关注算法所执行的计算步骤随输入规模增长的趋势。这是因为实际的运行时间会受到许多难以量化且随机的系统因素影响。因此，我们只跟踪计算步骤的增长，并假定每个步骤的耗时相等。

为了更好地说明时间复杂度分析，请看下面的示例：

假设我们有一个用户列表，其中每个用户都包含ID和姓名信息。现在我们需要实现一个函数，在给定用户ID时返回用户名。一种实现方式如下：

users = [
    {'id': 0, 'name': 'Alice'},
    {'id': 1, 'name': 'Bob'},
    {'id': 2, 'name': 'Charlie'},
]

def get_username(id, users):
    for user in users:
        if user['id'] == id:
            return user['name']
    return 'User not found'

get_username(1, users)

对于一个给定的用户列表，我们的算法会遍历整个用户数组，直到找到具有匹配ID的用户。当列表中有3个用户时，算法会执行3次迭代；当有10个用户时，则执行10次迭代。

可见，算法的执行步骤数与用户数量呈线性关系。因此，该算法的时间复杂度是线性的。但是，我们还可以优化此算法。

假设我们不是将用户存储在列表中，而是将其存储在字典中。那么，我们查找用户的算法如下：

users = {
    '0': 'Alice',
    '1': 'Bob',
    '2': 'Charlie'
}

def get_username(id, users):
     if id in users:
         return users[id]
     else:
         return 'User not found'

get_username(1, users)

使用新的算法，假设字典中有3个用户，我们需要执行固定数量的步骤来获取用户名。如果用户数量增加到10个，我们仍然只需要执行相同数量的步骤。随着用户数量的增长，获取用户名的步骤数量保持不变。

因此，这个新的算法具有恒定的时间复杂度。无论有多少用户，执行的计算步骤数量都是相同的。

什么是大O符号？

在前文中，我们讨论了如何计算不同算法的大O空间复杂度和时间复杂度，并用线性或常数等词汇来描述复杂度。大O符号是另一种描述复杂度的常用方法。

大O符号是一种表示算法空间或时间复杂度的表示方式。它以”O”后跟一个括号的形式呈现，括号内是一个关于输入规模n的函数，用来表示特定的复杂度。

线性复杂度用n来表示，所以我们将其写成O(n)（读作“O of n”）。常数复杂度用1表示，所以写成O(1)。

还有其他更多类型的复杂度，我们将在下一节讨论。总的来说，要计算算法的复杂度，可以遵循以下步骤：

尝试推导一个关于n的数学函数f(n)，其中f(n)表示算法使用的空间量或计算步骤，n是输入规模。
选择该函数中增长速度最快的项。各项的增长速度由快到慢依次为：阶乘、指数、多项式、二次、线性、对数、常数。
删除该项的所有系数。

最终的结果就是我们在括号中使用的表达式。

举个例子：

考虑以下Python函数：

users = [
    'Alice',
    'Bob',
    'Charlie'
]

def print_users(users):
    number_of_users = len(users)
    print("Total number of users:", number_of_users)

    for i in number_of_users:
        print(i, end=': ')
        print(user)

现在，我们来计算一下这个算法的大O时间复杂度。

首先，我们用一个数学函数f(n)来表示算法执行的计算步骤数。回想一下，n代表输入规模。

从代码可以看出，该函数执行两个操作：一是计算用户数量，二是打印用户数量。接着，对于每个用户，它执行两个操作：一是打印索引，二是打印用户。

因此，表示计算步骤数的函数可以写成f(n) = 2 + 2n。其中n代表用户数量。

接着第二步，我们选择增长最快的项。2n是一个线性项，2是一个常数项。线性项的增长速度比常数项快，因此我们选择2n，即线性项。

所以，我们的函数现在是f(n) = 2n。

最后一步是删除系数。在我们的函数中，系数是2，我们将其删除。函数就变成了f(n) = n。这就是我们在括号中使用的项。

因此，此算法的时间复杂度是O(n)，也就是线性复杂度。