这是我的促销信息，鼓励你更好地分享自己的知识和经验！ 看到的你也谢谢你给我很多支持！
1 .滴滴云AI master :目前滴滴云正在大力推广自己的云计算服务，需要购买的朋友可以使用我的AI master码“2049”，在滴滴云上335555535353350
原文地址：7 Helpful Time Complexities原文作者： Ellis Andrews译文：掘金翻译计划正文永久链接： https://github.com/xitu/gold-miner/blob/master/article7- helpful-time-complexities.MD译者： PingHGao校对者： rachelcdev，Isildur46算法常见七种时间复杂度
作为程序员，我努力写尽可能高效的代码。 但是，我怎么知道我们写的代码是否高效？ 答案：大o分析。 本文的目的是用尽可能简单的术语解释这个概念。 首先介绍Big O，然后举例说明你可能遇到的七种最常见的情况。 如果您已经熟悉了这个概念，并想使用实际的Python代码进行具体复习，请随时进入第2部分。
我像五岁一样解释我：大o版
简而言之，用“大o表示法”来表达算法的效率。 具体来说，记述了算法输入任意增加时，算法的执行时间会如何变化。 这是个简洁的定义，但我不知道哪个5岁的孩子能理解这个表达方式，让我详细说明一下。 有以下定义。
3358 www.Sina.com/http://www.Sina.com /作用于输入以产生输出的一组逻辑步骤。
本文将GPU与更亲近的概念联系起来。vGPU请回想一下创建的大多数函数的功能。 将一个或多个参数作为输入，对这些参数执行指定的操作步骤，然后作为输出返回值。 别害怕这句花里胡哨的话，你可能已经写了很多算法！ 从现在开始，当你说“算法”时，你可以直接把它理解为“函数”。
3358 www.Sina.com/http://www.Sina.com /算法需要执行的操作数。
无论算法是以秒、分钟或小时等时间单位测量的，都有许多因素影响特定计算机上算法的运行时间。 因此，最大o表示法根据根据需要执行的3358www.Sina.com/定义了执行时间，而不是关注在其中执行算法的实际机器学习产品。 较少的操作需要更短的运行时间(更高效)，较多的操作比较长的运行时间(更高效)。 因此，有比较算法的标准方法。
9算法需要处理的数据量。
在大o表示法中，随着数据输入量的增加，通过算法关注性能方面的差异。 例如，如果需要从三个随机数的列表中查找最大值，则可能有能力创建一些函数以在相似程度上优化他们的性能。 但是，如果列表中包含100个数字该怎么办？ 1,000？ 1000，000呢？ 这就是我们所说的“输入规模任意增大”，大o表示法有时也被称为“渐近分析”。 在大o表示法中，用“1. 算法”表示输入规模。
除运行时外，还可以使用大型o表示法来描述算法根据输入大小占用空间(内存、磁盘等)的程度。 本文将重点介绍时间的复杂性。
既然我们已经知道如何读写大o，那到底怎么写呢？ 那么，其写法是大写的“o”，后面有括号。 括号里有“n”，也就是包含输入规模的公式。 以下是最常见的7个例子。 按执行效率高的顺序排序。
—常数复杂度算法对数复杂度3358www.Sina.com/线性复杂度函数对数线性复杂度3358 ww.Sina 指数复杂度3358www.Sina.com/阶乘复杂度下图显示了在各种复杂度的算法中，输入越大操作数(执行时间)越变化的倾向。
如您所见，随着输入规模的增大，红色阴影区域算法的执行时间急剧增加。 另一方面，黄色和绿色阴影区域中的算法在处理大量数据时效率更高，因为输入规模越大，执行时间变化也越小。
最后，大型o表示法通常用于描述输入规模非常大时算法表现出的“显著趋势”。 因此，大的显著趋势涵盖细枝末节的趋势。 例如，我们实际计算的时间复杂度为2. 运行时间的算法
ong>O(n²)，原因是随着 n 变得非常大时， n² 这一项的显著性远远盖过了 n 这一项的显著性。 例子现在，让我们看一下上述每种复杂度的算法对应的一些常见例子。
1. O(1) — 常数复杂度这种复杂度的算法的运行时间不会随着输入规模的增加而增加。这类操作的实际例子就是在数组中按索引查找值，或者在哈希表中按键查找值：
from typing import Any, Dict, List# 例 1def list_lookup(list_: List[Any], index: int) -> Any: """Lookup a value in a list by index.""" return list_[index]# 例 2def dict_lookup(dict_: Dict[Any, Any], key: Any) -> Any: """Lookup a value in a dictionary by key.""" return dict_[key]无论传递给这些函数的列表或字典有多大，它们用同等的时间来完成（只有一步操作）。
2. O(log n) — 对数复杂度典型的对数复杂度算法是二分搜索算法。这是一种用于在有序数组中查找特定值的算法，它不断迭代读取当前范围的中间值，判断目标值是小于还是大于中间值，排除不包含目标的那一半内容。下面是它的一种实现：
from typing import Any, Listdef binary_search(list_: List[int], target_value: int) -> int: """ 对有序的输入列表执行二分搜索以找到目标值。 返回列表中目标值的索引，如果未找到则返回 -1。 """ # 初始化左右索引以开始搜索 left = 0 right = len(list_) - 1 # 执行二分搜索 while left <= right: # 计算要搜索的剩余列表的中间位置的索引 middle = left + (right - left) // 2 # 检查目标值是否在中间索引处。如果是，我们已经找到并完成。 if list_[middle] == target_value: return middle # 如果目标值大于中间值，请忽略剩余列表的左半部分 elif list_[middle] < target_value: left = middle + 1 # 如果目标值小于中间值，请忽略剩余列表的右半部分 else: right = middle - 1 # 如果在整个列表中未找到目标值，则返回 -1 return -1由于每次迭代，待搜索的数组长度会减半。因此哪怕搜索的数组长度翻了一倍，也只需多迭代一次！因此，随着数组长度的增加，运行时间将呈对数增长。
3. O(n) — 线性复杂度线性复杂度算法往往在连续迭代数据结构时涉及到。参考先前的对数搜索示例，在数组中搜索值可以用（效率较低）的线性时间来进行：
from typing import Any, Listdef linear_search(list_: List[Any], target_value: Any) -> int: """ 对输入列表执行线性搜索以找到目标值。 返回列表中目标值的索引，如果未找到则返回 -1。 """ # 遍历列表中的每一项，检查其是否为目标值 for index, item in enumerate(list_): if item == target_value: return index # 如果在列表中未找到目标值，则返回一个标记值 return -1显然，随着输入列表大小的增加，由于需要检查列表中的每个项目，最坏情况下找到目标所需的循环迭代次数的增长与输入列表的大小增长成正比。
4. O(n log n) — 对数线性复杂度列举对数线性复杂度算法的示例会比之前难一些。sfdxd，它们同时包含对数和线性部分。其中最常见的示例是排序算法。有一个算法叫「归并排序」，它用迭代手法将数组分成一小块一小块，对每小块进行拆分、排序，然后再按顺序重新将各个小块合并在一起。通过图像可以更容易看明白，因此我将省略代码的实现。
5. O(nᵏ) — 多项式复杂度在这里，我们开始着手研究时间复杂度较差的算法，通常应尽可能避免使用它（请参考上文的图表，我们正处于红色区域！）。但是，许多「暴力」算法都属于多项式复杂度，可以作为帮助我们解决问题的切入点。例如，下面是查找数组中重复项的二次（k = 2）多项式算法：
from typing import Any, List, Setdef find_duplicates(list_: List[Any]) -> Set[Any]: """查找列表中所有的重复项。""" # 初始化一个集合以保存重复项 duplicates = set() # 将列表中的每一项与列表中的其他所有项进行检查 for index_1, item_1 in enumerate(list_): for index_2, item_2 in enumerate(list_): if index_1 != index_2 and item_1 == item_2: duplicates.add(item_1) # 返回重复项的集合 return duplicates对于数组中的每一项，我们都将其数组其余各进行检查。因此，如果数组包含 n 个项目，我们将执行 n * n = n² 个运算，时间复杂度为 O(n²)。
附加题：你能想出更好的算法来解决此问题吗？
6. O(kⁿ) — 指数复杂度我们的倒数第二个常见时间复杂度是指数复杂度，即随着输入规模的增加，运行时间将按固定倍数来增长。一个典型的例子是直接计算斐波纳契数列中的第 n 项。
def nth_fibonacci_term(n: int) -> int: """递归计算斐波纳契数列的第 n 项。假设 n 是整数。""" # 基本情况 —— 前两项的值为 {0，1} if n <= 2: return n - 1 return nth_fibonacci_term(n - 1) + nth_fibonacci_term(n - 2)在上面的示例中，每当输入 n 增加 1 时，执行的操作数量就会翻倍。这是因为我们没有缓存每个函数调用的结果，所以必须从最开始重新计算所有先前的值。因此，该算法的时间复杂度为 O(2ⁿ)。
7. O(n!) — 阶乘复杂度最后但同样重要（但肯定是效率最低）的类型是阶乘时间复杂度的算法。通常应避免这中复杂度，因为随着输入规模的增加，它们会很快变得难以运行。这种算法有一个示例，那就是旅行推销员问题的暴力解法。这个问题是希望找到一条最短路径，要求该路径必须访问坐标系中的所有点，并最终回到起点。暴力解法涉及相互比较所有可能的路线（读作：排列组合）并选择最短的。请注意，除非要访问的点数很少，否则这通常不是解决此问题的合理方法。
结语尽管我们在这里介绍了很多案例，但在该主题上还有很多东西要学习！我关注的是“最坏情况下的时间复杂度”，但考虑平均情况或最佳情况也很有用。我也没有提到空间的复杂性，如果内存有限，这也同样重要。好消息是，这种分析的方法和一般思考过程是相同的。希望下次您进行代码面试时或需要编写性能函数时，你有了可以放心地解决它的工具。
如果发现译文存在错误或其他需要改进的地方，欢迎到 掘金翻译计划 对译文进行修改并 PR，也可获得相应奖励积分。文章开头的 本文永久链接 即为本文在 GitHub 上的 MarkDown 链接。
息是，这种分析的方法和一般思考过程是相同的。希望下次您进行代码面试时或需要编写性能函数时，你有了可以放心地解决它的工具。
如果发现译文存在错误或其他需要改进的地方，欢迎到 掘金翻译计划 对译文进行修改并 PR，也可获得相应奖励积分。文章开头的 本文永久链接 即为本文在 GitHub 上的 MarkDown 链接。
掘金翻译计划 是一个翻译优质互联网技术文章的社区，文章来源为 掘金 上的英文分享文章。内容覆盖 Android、iOS、前端、后端、区块链、产品、设计、人工智能等领域，想要查看更多优质译文请持续关注 掘金翻译计划、官方微博、知乎专栏。