最近我参加了一家我很想加入的很酷公司的面试，其中一步是令人头疼的现场编程面试，我们需要现场解决LeetCode上的编程题。
我找到了解决方案，当我被问到我解决方案的大O函数时，我正确地回答了，但我很困惑，可能是我只是简单地数了数循环，磕磕绊绊地说出的。
为了以后不再失败求职面试，尽管以前在大学时已经学过，我几年之后决定重新审视这个话题。
这篇文章的主要目的就是提供一个快速回顾，让我在编码面试前快速复习一下。虽然我通过写作来学习知识，但也很重要的是，这使得我可以随时查阅。而且，说不定对你也有帮助哦。
非常感谢NeetCode提供了这么多免费的材料，并教了这么多东西。真的太感谢了。
什么是时间复杂度中的O表示法？在计算机科学中，大O记号被用来根据输入大小增加时算法的运行时间或空间需求的增长情况来分类算法。 [...] [它] 根据增长速率来刻画函数：具有相同渐进增长率的不同函数可以使用相同的O记号来表示。
- 来源：维基百科
或者说，这是一种分析我们的算法运行时间随着输入量增长而变化的方法。O 代表整个操作过程，而 n 则代表输入量。
让我们看看一些例子，这样会更明白。
O(n) - 行吧，给我举个例子吧也许最易理解的例子是 O(n)，其增长速度是线性的。
- 给定未排序的数组 n，编写一个函数来返回最大值。
我们需要遍历数组 n 中的每个项目，并在找到比之前更大的值时存储起来。
n = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] # 定义数组 n
def find_max_value(arr):
# 将最大值初始化为数组的第一个元素
max_value = arr[0]
# 遍历数组以找到最大值
for num in arr:
if num > max_value:
max_value = num
return max_value
print(find_max_value(n)) # 打印最大值进入全屏、退出全屏
前面的算法至少会检查一次n中的每个元素——它不得不这样做，因为数组是乱序的。
因此可以说，这个算法的时间复杂度为 O(n)，因为随着数组大小的增长，运行时间随数组大小线性增加。
它也不关心你算法中的非恒定参数。想象一下，你的算法恰好遍历了你的 n 中的每个元素两次，导致时间复杂度为 O(2n)。我们简化它，说它是 O(n)，因为大 O 表示法的首要任务是描述运行时间的增长趋势。
O(1): 唯一的一个例外在告诉你我们不必在意那些非恒定值之后，我们还需要谈谈 O(1) 。这里甚至没有涉及到 n 。这可能是最理想的效率，时间不会随着输入的增加而增加，始终保持不变。例如：
给一个非空数组，返回数组的第一个元素。
n = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] # 将 n 定义为数组
def first_element(arr):
# 返回数组的第一个值
return arr[0]
print(first_element(n)) # 输出结果为 3全屏显示 取消全屏
因为我们实际上并没有遍历数组中的任何元素，所以这个操作的时间复杂度是 O(1)。
例如，向数组添加项或弹出（pop）。在使用哈希表（或字典）时，我们只需通过键查找，就像上面提到的算法一样。
最简单的情况是，在这种情况下你有嵌套的循环，或者是一个二维数组，你需要遍历它们来找到你要找的东西。
给定骰子的面数时，计算使用两颗相同面数的骰子所产生的每一种可能的组合。
def 骰子组合可能性(sides):
# 初始化组合可能性数组
组合可能性 = []
# 遍历每一面
for i in range(1, sides + 1):
# 添加所有可能的组合可能性
for j in range(1, sides + 1):
组合可能性.append((i, j))
return 组合可能性
面 = 6 # 示例，6面骰子
print(骰子组合可能性(面))
# 输出：包含36个组合（6 * 6）
# [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]
全屏 退出全屏
那么但如果骰子有不同的面会怎么样？
O(n*m) - 行了，你现在只是在随便加字母了如果需要用两个不同面数的骰子来计算可能的组合，它们将会如下所示。
- 给定两个骰子的面数后，算出这两个骰子所有可能的组合结果。
def two_dice_combinations(sides1, sides2):
# 初始化组合数组
combinations = []
# 遍历第一个骰子的所有面
for i in range(1, sides1 + 1):
# 将所有可能的组合添加到列表中
for j in range(1, sides2 + 1):
combinations.append((i, j))
return combinations
sides1 = 6 # 比如，一个6面的骰子
sides2 = 8 # 另一个例子是，一个8面的骰子
print(two_dice_combinations(sides1, sides2))
# 输出结果是一个包含48个元素的数组（6 * 8）
# 每个元组代表两个骰子可能的组合结果，例如(1,1)表示两个骰子都掷出1面
# [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8)]切换到全屏 退出全屏
请记住，这些可以一直运行下去。如果有三个骰子，你可以有一个O(n^3)的算法，也可以是O(n^5)\ - 数学并没有限制。比如，这会变成O(n^3)或者甚至O(n^5)。
O(log n) - 这是什么？大多数人甚至不明白 log 是什么意思，只是记住这种记号通常会在进行二分搜索时用到。
这是每次迭代时，我们将循环的范围减半的情况。因此，log n 就变成了 我们能将 n 除以 2 几次才能得到结果。例如，如果我们从 n 开始，每次迭代都除以 2，直到结果为 1，这就是 log n 的概念。这也就是当底数为 2 时，log 记号的定义。
当处理二叉树中的三时，我们需要遍历每个节点，在每个节点上我们都需要做出决定，选择往左或往右。这样我们每次只需要处理一半的操作，忽略每个节点的子节点数量可能不同。
这是最好的算法之一，可以说它是最佳算法之一，因为它的运行时间几乎不会增加。对于非常大的输入规模，时间几乎保持不变。
执行二分搜索是常见的 O(log n) 情况，这种情况更符合技术讨论中的常用表达。
我不会详谈，但简单来说，当我们有一个排序好的数组，想要查找特定值的索引时，就可以用二分查找。
- 在已排序的数组中，找到目标值的索引位置
def binary_search(arr, target):
# 初始化左右指针为数组的第一个和最后一个元素
left, right = 0, len(arr) - 1
# 当左指针小于或等于右指针时继续搜索
while left <= right:
# 计算中间索引：
mid = (left + right) // 2
# 检查中间元素是否为目标
if arr[mid] == target:
return mid
# 如果中间元素小于目标，将左指针调整为
elif arr[mid] < target:
left = mid + 1
# 如果中间元素大于目标，将右指针调整为
else:
right = mid - 1
# 未找到目标时返回 -1
return -1
# 示例用法：
有序数组 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
目标 = 7
print(binary_search(有序数组, 目标)) # 输出：6 - 有序数组[6] == 7
进入全屏 退出全屏
注意，循环不是常见的for i in range(1, n)形式，而是位于left和right索引之间的中间位置。
之所以这么做是因为这很难直观理解。
这种符号常出现在排序算法中，事实上，它是现代编程语言中内置排序函数中最常见的符号。
以 归并排序 为例。为了不陷入过多细节，它基本上通过将数组递归地分成两半（每次划分的时间复杂度为 log n），然后再将这两半以线性时间合并。每次合并所需时间为 O(n)。通过结合这两个步骤，这样我们就得到 *O(n log n)** 的时间复杂度。
- 给定一个乱序数组，用合并排序来把它排好序。
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 找到中间点，将数组分成两半
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 递归地对两半进行排序
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
# 合并两个有序的半部分
return merge(left_sorted, right_sorted)
def merge(left, right):
sorted_array = []
left_index, right_index = 0, 0
# 合并两个数组并保持有序
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
sorted_array.append(left[left_index])
left_index += 1
else:
sorted_array.append(right[right_index])
right_index += 1
# 添加来自左或右数组的任何剩余元素
sorted_array.extend(left[left_index:])
sorted_array.extend(right[right_index:])
return sorted_array
# 示例用法如下：
unsorted_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(merge_sort(unsorted_array)) # 输出：[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
全屏播放 退出全屏
从上面的代码中我们可以看到，每次调用 merge_sort 时，它都会通过调用 merge 结束。而且每次调用 merge_sort 时，它还会递归调用自己两次，分别对应数组的一半。
这种表示法通常出现在我们有一个递归函数，在两种情况下分支时。
我们可以很容易地看到这些复杂性，在冒泡排序中。但是谈到算法就不得不提到斐波那契，我们终于来谈谈它吧。但记住，还有更有效的方法来解决这个问题。
- 给定一个索引，找到斐波那契数列里相应位置的那个数字
def 斐波那契数列(n):
if n <= 1:
return n
前一项 = 斐波那契数列(n-1)
次前一项 = 斐波那契数列(n-2)
return 前一项 + 次前一项
# 示例用法如下：
print(斐波那契数列(5)) # 输出：5进入全屏
退出全屏
可以看出，上面的实现表明，在每次递归循环迭代过程中都会创建两个分支。
例如，对于 n = 5，我们会调用 fibonacci(4) 和 fibonacci(3)，其中 fibonacci(3) 又会被调用一次（因为我们在算法中还没有实现记忆功能），fibonacci(2) 也会被调用两次，以及 fibonacci(1)。你可以想象它是一个“倒置的二叉树”，其中树的高度为 n。
理论上来说，我们可以将任意数字提升到 n 次方，比如像 O(3^n) 这种形式，还有像 O(5^n)。
O(n!) - 让它快点结束吧，拜托！如果你不知道 ! 是什么意思，我们只需将该数字乘以该数字减1的结果，直到乘积变为1为止。
例如：
5! = 5 4 3 * 2 = 120
你可以把它想象成一种算法，每次迭代时移除一个项目，然后再重新运行。这种算法主要出现在排列组合中，或者更著名的是在旅行商问题中。
对于这一种情况，我不会添加任何代码片段，因为这会非常复杂，而且这种情况极其罕见，基本上不会遇到。因为如果你的算法复杂度是 O(n!)，那肯定不是最优解，可以继续优化。
就这样吧！你可以看看下面的图表，了解这些算法的比较情况。纵轴表示操作次数（也就是时间），横轴表示元素数量（也就是n的值）。特别感谢 Eric Rowell 提供的这份参考资料！
你可以在这里查看更多详情 https://www.bigocheatsheet.com/
我希望这篇文章对你有帮助，祝你在今后的学习中一切顺利！
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
