Ruby 课程计算机科学篇Big O 与时间复杂度完整指南【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum时间复杂度是衡量算法效率的核心工具。本篇文章基于开源课程 cu/curriculumThe Odin Project 风格的 Web 开发开放课程中 Ruby 计算机科学模块的《Time Complexity》一课系统讲解为什么不能靠秒表计时衡量代码快慢、如何用步骤计数法分析算法、Big O / Omega / Theta 三种渐近记号的区别以及 O(1)、O(log N)、O(N)、O(N log N)、O(n²)、O(n³)、O(2ⁿ)、O(N!) 八种常见复杂度的判定方法。学完本文你将能够对任意 Ruby 代码循环、嵌套循环、递归、二分查找、排序算法进行复杂度分析并为后续的哈希表、二叉搜索树、BFS/DFS 等数据结构与算法课程奠定分析基础。为什么要关心代码的效率写代码到一定阶段你会从让代码能跑过渡到让代码好读、好维护。可读性和可维护性固然重要——你读代码的时间很可能不亚于写代码的时间——但还有一个同样关键的维度效率Efficiency。你需要理解自己写出的代码将如何运行理解每一个选择数据结构、算法、写法如何影响性能才能在需求面前选出正确的数据结构与算法。在编程中衡量代码效率有两种方式时间复杂度Time Complexity衡量算法运行所需的步骤数如何随输入规模变化。空间复杂度Space Complexity衡量算法运行所需的内存如何随输入规模变化。这部分内容在课程中由 space_complexity.md 一课专门讲解。本文聚焦时间维度。为什么不能用运行时间衡量效率先看课程给出的第一个例子打印 1 到 10 之间的所有奇数。def odd_numbers_less_than_ten current_number 1 while current_number 10 if current_number % 2 ! 0 puts current_number end current_number 1 end end在终端运行它会输出1、3、5、7、9整个过程可能只花了不到一秒。但如果再运行一次耗时可能相同、也可能更快或更慢——取决于此刻计算机还在忙什么换一台电脑运行结果又会不同。这就是关键结论永远不要用实际执行时间来衡量一个算法的效率。执行时间受硬件、系统负载、语言实现等无关因素干扰无法作为可比较的度量。步骤计数法算法效率的度量方式正确的度量方式是数步骤一个算法完成同样的任务需要 5 步另一个需要 20 步那么在同一台计算机上5 步的算法永远比 20 步的快。回到odd_numbers_less_than_ten逐条数它的步骤把数字 1 赋给变量current_number1 步。循环的每次迭代比较current_number是否小于 101 步检查current_number是否为奇数1 步若是奇数则输出到终端每 2 次迭代 1 步current_number 11 步。退出循环前最后一次比较current_number是否不再小于 101 步。汇总每次迭代约 3 步循环 9 次共 27 步输出操作约 5 步9 次迭代中约一半加上变量初始赋值 1 步、退出条件比较 1 步。总计 27 5 1 1 34 步。这个数字本身是有用的信息但对比较算法没有帮助。为什么把方法稍作修改接受一个参数而不是写死 10def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 1 end end现在步骤数是多少答案取决于传入的max_number。传 10 时是 34 步传其他值步数就变了。不存在一个固定的数字可以用来衡量这段代码的效率因为它随外部输入变化。我们真正想衡量的是当数据变化时算法的步骤数如何变化——这才能回答代码能否规模化scale的问题。这正是渐近记号Asymptotic Notations要解决的事情。渐近记号Big O、Omega 与 Theta渐近记号用来描述算法的运行时间。由于运行时间随输入不同而不同存在三种常见记号从不同角度测量记号含义场景Big O大 O算法的上界最坏情况worst-case下算法如何表现Omega大 Ω算法的下界最好情况best-case下算法如何表现Theta大 Θ同时包含上界与下界平均情况average-case下的复杂度Big O 是最常被引用的记号因为你需要确保任何代码的最坏情况都能在输入增长时保持可扩展。后面列出的八种复杂度记号同样适用于 Omega 与 Theta区别只在于它们衡量效率的角度不同。什么是 Big OBig O 提供了一种一致的方法来衡量算法效率它度量当输入增长时算法运行时间的变化趋势从而让你能直接比较两个算法的性能并选出更优者。需要澄清的是Big O 并不是一段把你的算法放进去就能算出效率的代码。你需要自己测量步骤数如何随数据增长而变化再据此套用对应的 Big O 记号。在多数情况下你使用的数据结构其常见操作的复杂度是已知的例如哈希表的增删查、数组的按下标访问这时就很容易判断它随输入变化会如何扩展。八种常见 Big O 复杂度按速度从快到慢课程给出了最常用 Big O 记号的速查表记号名称O(1)常数复杂度Constant ComplexityO(log N)对数复杂度Logarithmic ComplexityO(N)线性复杂度Linear ComplexityO(N log N)N × log N 复杂度O(n²)平方复杂度Quadratic ComplexityO(n³)立方复杂度Cubic ComplexityO(2ⁿ)指数复杂度Exponential ComplexityO(N!)阶乘复杂度Factorial Complexity下面逐一拆解每种复杂度并给出 Ruby 示例与判定方法。O(1)常数复杂度用数组来理解常数复杂度arr [1, 2, 3, 4, 5]想取索引 2 处的元素用arr[2]一次即可拿到3只需 1 步。把数组翻倍arr [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]arr[7]依然 1 步返回8。数组无论多大按下标访问任意元素都是 1 步——恒定的所以是 O(1)。按单步完成查找已经是时间复杂度能到达的最好情况。这里有一个 Big O 的常见陷阱真的是 1 步吗严格来说不是——计算机需要先找到数组在内存中的位置再从首元素跳到参数指定的索引至少是几步。所以写成O(1 2(steps))也不能说错。但这 2 步只是附带开销incidental数组有 10,000 个元素时它依然是同样的步数。Big O 不关心这类常数因为它们在数据规模变化时不提供任何复杂度增长的信息所以在 Big O 中会被丢弃。Big O 只关心算法复杂度相对于输入规模的关系。O(log N)对数复杂度对数复杂度的含义是数据翻倍时算法步骤数只增加 1。从 5,000 个元素增长到 10,000 个元素只多 1 步扩展性非常好。最典型的 O(log N) 算法是二分查找Binary Search。它只适用于有序数组。假设有序数组arr [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]要确认数组里是否包含数字7二分查找用公式计算中间索引middle_index (start_index end_index) / 2其中start_index初始为 0end_index初始为 910 个元素的数组。中间元素是索引 4 处的5。因为数组有序且7 5可以排除5及其左侧所有元素它们都小于 7arr [-, -, -, -, -, 6, 7, 8, 9, 10]仅仅 1 步就排除了一半数组。接着用新的start_index、end_index重算中间索引此时中间索引是 7该位置是8。由于7 8排除8及其右侧所有元素arr [6, 7, -, -, -]重复这个过程直到数组只剩 1 个元素若该元素匹配要找的数则找到否则说明该数不在数组中。下表总结了数组大小翻倍时Big O 意义上需要多少步才能收敛到 1 个元素规模步数11224384165326这正是对数增长的威力规模每翻倍一次只需多 1 步。O(log N) 复杂度在课程后续的二叉搜索树课程 project_binary_search_trees.md 中还会反复出现——该课程明确指出二叉搜索树的插入/删除可以达到 O(log n)相比数组的同类操作是显著的性能提升。O(N)线性复杂度线性复杂度最容易理解元素数量增长多少步骤数就以同样的速率增长多少。每次遍历数组都是线性复杂度的例子。5 个元素的数组用 5 步遍历完10 个元素用 10 步。凡是 Big O 为 O(N) 的算法其步骤数都会与数据结构中的元素数量同步增长。课程中反复出现的odd_numbers方法就是 O(N) 的典型输入规模增大步骤数以相同速率增加。O(N log N)N × log N 复杂度这个记号的意思是算法一开始是 O(log N)如二分查找那样反复把数组对半切分但每一半都要再被一个 O(N) 复杂度的算法处理于是得到 O(N log N)。最典型的例子就是课程上一节项目课中实现的归并排序Merge Sort——它在 project_recursion.md 中通过递归分而治之把排序问题不断拆分为更小的子问题再按序合并回去。归并排序正是 O(N log N) 复杂度的代表作拆分阶段是对数级而每一层的合并操作整体是线性的。O(n²)平方复杂度平方复杂度很常见在一个数据集上循环循环体内又对整个数据集循环一次嵌套循环。例如数组有 3 个元素时嵌套循环需要 3² 9 个子步骤加 1 个元素几乎让工作量翻倍到 4² 165 个元素是 5² 25把数组翻倍到 10 个元素子步骤从 25 暴涨到 100——工作量变成原来的 4 倍# 双层嵌套循环的典型形态 arr.each do |i| arr.each do |j| # 每对 (i, j) 都是一个子步骤 end end平方复杂度提示输入翻倍工作量变成 4 倍。O(n³)立方复杂度立方复杂度对应三重嵌套循环。对 n 个元素的数组增加 1 个元素意味着多一层外层循环、一层中层循环和一层最内层循环总子步骤为 n³。3 个元素需要 3³ 27 个子步骤4 个元素是 4³ 64增加一个元素就翻了一倍多5 个元素是 5³ 125数组翻倍到 10 个元素需要 10³ 1000 个子步骤是原来的 8 倍100 个元素则需要 1,000,000 个子步骤。O(2ⁿ)指数复杂度指数复杂度的含义是每增加一个数据项步骤数相对之前翻倍。下表展示了它失控的速度规模步数122438416532664712882569512101024能避免就尽量避免否则你处理不了多少数据就会卡死。O(N!)阶乘复杂度一个数的阶乘是 1 到该数之间所有整数的乘积例如 4! 4 × 3 × 2 × 1 24。当你需要计算排列或组合时会遇到阶乘复杂度给定一个数组穷举它能组成的所有组合就是阶乘复杂度。少量元素时还可控但每增加一个数据项跳跃幅度都极其惊人3! 64! 2410! 3,628,800。可以看到规模稍微一大计算量立刻失控。Big O 之外的衡量方式Omega 与 Theta如果 Big O 给出的是最坏情况那还有哪些替代记号Big ΩOmega 记号Omega 记号给出算法最好情况的复杂度。看课程中的例子def find_value(arr) arr.each do |item| return item if item 1 end end最坏情况Big O发生在要找的值不在数组中、或是数组最后一个元素时算法需要遍历每个元素复杂度为 O(N)——输入规模翻倍最坏情况下的迭代次数也翻倍。但在最好情况下要找的值是数组的第一个元素算法只需 1 步复杂度为 Ω(1)这就是它的 Omega 复杂度。Omega 记号被认为没那么有用因为目标值很少恰好是数据结构中的第一个元素它无法告诉我们算法在实际中如何扩展。Big ΘTheta 记号Omega 衡量最好情况、Big O 衡量最坏情况而 Theta 试图给出精确值或在窄的上界与下界之间给出有用的范围。如果一段代码遍历数组中的每个元素那么无论数组多大最好情况和最坏情况都是 O(N) 时间可以确定它在所有场景下的精确性能是 Θ(N)。对于其他算法Theta 可能同时代表不同复杂度的下界与上界。这里不再深入因为 Big O 是描述一般算法时间复杂度最常用的记号。为什么用 Big O最坏情况理解了三种记号之后选择最坏情况来衡量算法效率的理由就清楚了用最坏情况能确保算法在所有结果下都可扩展。如果一个算法可能以常数时间运行、但最坏情况下是线性时间那么只有最坏情况也能扛住它才能随输入增长而扩展。你必须确信当输入突然从 10 个变成一百万个时代码不会卡死、不会让用户干等。相同复杂度的算法为什么常数会被丢弃两个算法复杂度相同就代表它们一样好吗课程用两个代码示例回答这个问题。第一个是我们已经见过的odd_numbers时间复杂度 O(N)def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 1 end end第二个改动很小——每次递增 2def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 2 end end对输入 n第二个版本每次迭代跳过 2步骤数约为原来的一半可以写成 O(N/2)。但正如前面所说Big O 追求的不是精确时间而是时间随输入规模增长的关系。Big O 不关心常数因为常数与算法随输入如何扩展无关——如果要在 O(N/2 5N) 与 O(N 5/2N) 之间比较那既不有趣也不方便。因此两个算法的 Big O 效率都是 O(N)它们随输入增长的比例速率相同。换个角度看常数最终会变得无关紧要。看下面的对比O(10N) 与 O(n²)NO(10N)O(n²)差距1101—55025—1001,00010,00010 倍1,00010,0001,000,000100 倍10,000100,000100,000,0001,000 倍所以当 N 达到 100 时O(10N) 快于 O(n²)。但从实践角度看对某些很小的输入集合n² 算法反而可能比 N 算法更快见上表前两行。这也提醒你在保证时间复杂度正确的前提下尽量让代码本身写得高效例如减少不必要的变量和遍历。复杂度分析在课程后续章节中的落地时间复杂度分析不是孤立的理论它贯穿整个计算机科学模块哈希表Hash Maphash_map_data_structure.md 一课明确给出哈希表的插入、检索、删除平均复杂度为 O(1)因为操作直接基于数组索引最坏情况为 O(n)发生在所有数据哈希到同一个桶、需要遍历链表时。这正解释了为什么课程强调设计良好的哈希函数以减少冲突。二叉搜索树BSTproject_binary_search_trees.md 指出 BST 的插入/删除可达到 O(log n)并专门提醒不要用原始输入数组实现这些操作否则会丢掉这一性能优势——这正是把本课的 O(log N) 分析应用于实际项目的实例。递归与分治recursive_methods.md 与 project_recursion.md 中的归并排序是 O(N log N) 的经典实现而递归深度过大会导致调用栈溢出——这既是时间复杂度的延伸也涉及空间复杂度。数据结构的权衡common_data_structures_algorithms.md 一课讨论栈、队列、链表以及 BFS/DFS 搜索算法时处处以操作耗时与内存占用的权衡为出发点project_linked_lists.md 中的链表操作at(index)需要从头遍历正是线性复杂度的实战案例。空间复杂度时间与空间是一体两面space_complexity.md 用与时间相同的 Big O 记号衡量内存使用并引入了辅助空间分析auxiliary space analysis的概念。知识自测回顾本课的核心问题检验自己是否掌握什么是 Big O它衡量的效率维度是什么最常见的 Big O 记号有哪些从快到慢如何排列为什么要使用 Big O最坏情况来衡量算法什么是 Big Omega为什么它没那么有用为什么 Big O 中常数不影响复杂度结论为什么不能用实际运行时间衡量算法效率O(log N) 算法在数据翻倍时步骤数如何变化此外课程的作业环节还推荐了外部资源包括面向 Ruby 开发者的 Big-O 指南、Big-O 速查表含各常见数据结构操作与排序算法的时间/空间复杂度对照以及更深入的 Ruby 时间复杂度专题文章可作为进阶阅读在完成本课后自行查阅。下一课将把同样的分析框架应用到空间维度请继续学习 space_complexity.md。【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Ruby 课程计算机科学篇：Big O 与时间复杂度完整指南
Ruby 课程计算机科学篇Big O 与时间复杂度完整指南【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum时间复杂度是衡量算法效率的核心工具。本篇文章基于开源课程 cu/curriculumThe Odin Project 风格的 Web 开发开放课程中 Ruby 计算机科学模块的《Time Complexity》一课系统讲解为什么不能靠秒表计时衡量代码快慢、如何用步骤计数法分析算法、Big O / Omega / Theta 三种渐近记号的区别以及 O(1)、O(log N)、O(N)、O(N log N)、O(n²)、O(n³)、O(2ⁿ)、O(N!) 八种常见复杂度的判定方法。学完本文你将能够对任意 Ruby 代码循环、嵌套循环、递归、二分查找、排序算法进行复杂度分析并为后续的哈希表、二叉搜索树、BFS/DFS 等数据结构与算法课程奠定分析基础。为什么要关心代码的效率写代码到一定阶段你会从让代码能跑过渡到让代码好读、好维护。可读性和可维护性固然重要——你读代码的时间很可能不亚于写代码的时间——但还有一个同样关键的维度效率Efficiency。你需要理解自己写出的代码将如何运行理解每一个选择数据结构、算法、写法如何影响性能才能在需求面前选出正确的数据结构与算法。在编程中衡量代码效率有两种方式时间复杂度Time Complexity衡量算法运行所需的步骤数如何随输入规模变化。空间复杂度Space Complexity衡量算法运行所需的内存如何随输入规模变化。这部分内容在课程中由 space_complexity.md 一课专门讲解。本文聚焦时间维度。为什么不能用运行时间衡量效率先看课程给出的第一个例子打印 1 到 10 之间的所有奇数。def odd_numbers_less_than_ten current_number 1 while current_number 10 if current_number % 2 ! 0 puts current_number end current_number 1 end end在终端运行它会输出1、3、5、7、9整个过程可能只花了不到一秒。但如果再运行一次耗时可能相同、也可能更快或更慢——取决于此刻计算机还在忙什么换一台电脑运行结果又会不同。这就是关键结论永远不要用实际执行时间来衡量一个算法的效率。执行时间受硬件、系统负载、语言实现等无关因素干扰无法作为可比较的度量。步骤计数法算法效率的度量方式正确的度量方式是数步骤一个算法完成同样的任务需要 5 步另一个需要 20 步那么在同一台计算机上5 步的算法永远比 20 步的快。回到odd_numbers_less_than_ten逐条数它的步骤把数字 1 赋给变量current_number1 步。循环的每次迭代比较current_number是否小于 101 步检查current_number是否为奇数1 步若是奇数则输出到终端每 2 次迭代 1 步current_number 11 步。退出循环前最后一次比较current_number是否不再小于 101 步。汇总每次迭代约 3 步循环 9 次共 27 步输出操作约 5 步9 次迭代中约一半加上变量初始赋值 1 步、退出条件比较 1 步。总计 27 5 1 1 34 步。这个数字本身是有用的信息但对比较算法没有帮助。为什么把方法稍作修改接受一个参数而不是写死 10def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 1 end end现在步骤数是多少答案取决于传入的max_number。传 10 时是 34 步传其他值步数就变了。不存在一个固定的数字可以用来衡量这段代码的效率因为它随外部输入变化。我们真正想衡量的是当数据变化时算法的步骤数如何变化——这才能回答代码能否规模化scale的问题。这正是渐近记号Asymptotic Notations要解决的事情。渐近记号Big O、Omega 与 Theta渐近记号用来描述算法的运行时间。由于运行时间随输入不同而不同存在三种常见记号从不同角度测量记号含义场景Big O大 O算法的上界最坏情况worst-case下算法如何表现Omega大 Ω算法的下界最好情况best-case下算法如何表现Theta大 Θ同时包含上界与下界平均情况average-case下的复杂度Big O 是最常被引用的记号因为你需要确保任何代码的最坏情况都能在输入增长时保持可扩展。后面列出的八种复杂度记号同样适用于 Omega 与 Theta区别只在于它们衡量效率的角度不同。什么是 Big OBig O 提供了一种一致的方法来衡量算法效率它度量当输入增长时算法运行时间的变化趋势从而让你能直接比较两个算法的性能并选出更优者。需要澄清的是Big O 并不是一段把你的算法放进去就能算出效率的代码。你需要自己测量步骤数如何随数据增长而变化再据此套用对应的 Big O 记号。在多数情况下你使用的数据结构其常见操作的复杂度是已知的例如哈希表的增删查、数组的按下标访问这时就很容易判断它随输入变化会如何扩展。八种常见 Big O 复杂度按速度从快到慢课程给出了最常用 Big O 记号的速查表记号名称O(1)常数复杂度Constant ComplexityO(log N)对数复杂度Logarithmic ComplexityO(N)线性复杂度Linear ComplexityO(N log N)N × log N 复杂度O(n²)平方复杂度Quadratic ComplexityO(n³)立方复杂度Cubic ComplexityO(2ⁿ)指数复杂度Exponential ComplexityO(N!)阶乘复杂度Factorial Complexity下面逐一拆解每种复杂度并给出 Ruby 示例与判定方法。O(1)常数复杂度用数组来理解常数复杂度arr [1, 2, 3, 4, 5]想取索引 2 处的元素用arr[2]一次即可拿到3只需 1 步。把数组翻倍arr [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]arr[7]依然 1 步返回8。数组无论多大按下标访问任意元素都是 1 步——恒定的所以是 O(1)。按单步完成查找已经是时间复杂度能到达的最好情况。这里有一个 Big O 的常见陷阱真的是 1 步吗严格来说不是——计算机需要先找到数组在内存中的位置再从首元素跳到参数指定的索引至少是几步。所以写成O(1 2(steps))也不能说错。但这 2 步只是附带开销incidental数组有 10,000 个元素时它依然是同样的步数。Big O 不关心这类常数因为它们在数据规模变化时不提供任何复杂度增长的信息所以在 Big O 中会被丢弃。Big O 只关心算法复杂度相对于输入规模的关系。O(log N)对数复杂度对数复杂度的含义是数据翻倍时算法步骤数只增加 1。从 5,000 个元素增长到 10,000 个元素只多 1 步扩展性非常好。最典型的 O(log N) 算法是二分查找Binary Search。它只适用于有序数组。假设有序数组arr [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]要确认数组里是否包含数字7二分查找用公式计算中间索引middle_index (start_index end_index) / 2其中start_index初始为 0end_index初始为 910 个元素的数组。中间元素是索引 4 处的5。因为数组有序且7 5可以排除5及其左侧所有元素它们都小于 7arr [-, -, -, -, -, 6, 7, 8, 9, 10]仅仅 1 步就排除了一半数组。接着用新的start_index、end_index重算中间索引此时中间索引是 7该位置是8。由于7 8排除8及其右侧所有元素arr [6, 7, -, -, -]重复这个过程直到数组只剩 1 个元素若该元素匹配要找的数则找到否则说明该数不在数组中。下表总结了数组大小翻倍时Big O 意义上需要多少步才能收敛到 1 个元素规模步数11224384165326这正是对数增长的威力规模每翻倍一次只需多 1 步。O(log N) 复杂度在课程后续的二叉搜索树课程 project_binary_search_trees.md 中还会反复出现——该课程明确指出二叉搜索树的插入/删除可以达到 O(log n)相比数组的同类操作是显著的性能提升。O(N)线性复杂度线性复杂度最容易理解元素数量增长多少步骤数就以同样的速率增长多少。每次遍历数组都是线性复杂度的例子。5 个元素的数组用 5 步遍历完10 个元素用 10 步。凡是 Big O 为 O(N) 的算法其步骤数都会与数据结构中的元素数量同步增长。课程中反复出现的odd_numbers方法就是 O(N) 的典型输入规模增大步骤数以相同速率增加。O(N log N)N × log N 复杂度这个记号的意思是算法一开始是 O(log N)如二分查找那样反复把数组对半切分但每一半都要再被一个 O(N) 复杂度的算法处理于是得到 O(N log N)。最典型的例子就是课程上一节项目课中实现的归并排序Merge Sort——它在 project_recursion.md 中通过递归分而治之把排序问题不断拆分为更小的子问题再按序合并回去。归并排序正是 O(N log N) 复杂度的代表作拆分阶段是对数级而每一层的合并操作整体是线性的。O(n²)平方复杂度平方复杂度很常见在一个数据集上循环循环体内又对整个数据集循环一次嵌套循环。例如数组有 3 个元素时嵌套循环需要 3² 9 个子步骤加 1 个元素几乎让工作量翻倍到 4² 165 个元素是 5² 25把数组翻倍到 10 个元素子步骤从 25 暴涨到 100——工作量变成原来的 4 倍# 双层嵌套循环的典型形态 arr.each do |i| arr.each do |j| # 每对 (i, j) 都是一个子步骤 end end平方复杂度提示输入翻倍工作量变成 4 倍。O(n³)立方复杂度立方复杂度对应三重嵌套循环。对 n 个元素的数组增加 1 个元素意味着多一层外层循环、一层中层循环和一层最内层循环总子步骤为 n³。3 个元素需要 3³ 27 个子步骤4 个元素是 4³ 64增加一个元素就翻了一倍多5 个元素是 5³ 125数组翻倍到 10 个元素需要 10³ 1000 个子步骤是原来的 8 倍100 个元素则需要 1,000,000 个子步骤。O(2ⁿ)指数复杂度指数复杂度的含义是每增加一个数据项步骤数相对之前翻倍。下表展示了它失控的速度规模步数122438416532664712882569512101024能避免就尽量避免否则你处理不了多少数据就会卡死。O(N!)阶乘复杂度一个数的阶乘是 1 到该数之间所有整数的乘积例如 4! 4 × 3 × 2 × 1 24。当你需要计算排列或组合时会遇到阶乘复杂度给定一个数组穷举它能组成的所有组合就是阶乘复杂度。少量元素时还可控但每增加一个数据项跳跃幅度都极其惊人3! 64! 2410! 3,628,800。可以看到规模稍微一大计算量立刻失控。Big O 之外的衡量方式Omega 与 Theta如果 Big O 给出的是最坏情况那还有哪些替代记号Big ΩOmega 记号Omega 记号给出算法最好情况的复杂度。看课程中的例子def find_value(arr) arr.each do |item| return item if item 1 end end最坏情况Big O发生在要找的值不在数组中、或是数组最后一个元素时算法需要遍历每个元素复杂度为 O(N)——输入规模翻倍最坏情况下的迭代次数也翻倍。但在最好情况下要找的值是数组的第一个元素算法只需 1 步复杂度为 Ω(1)这就是它的 Omega 复杂度。Omega 记号被认为没那么有用因为目标值很少恰好是数据结构中的第一个元素它无法告诉我们算法在实际中如何扩展。Big ΘTheta 记号Omega 衡量最好情况、Big O 衡量最坏情况而 Theta 试图给出精确值或在窄的上界与下界之间给出有用的范围。如果一段代码遍历数组中的每个元素那么无论数组多大最好情况和最坏情况都是 O(N) 时间可以确定它在所有场景下的精确性能是 Θ(N)。对于其他算法Theta 可能同时代表不同复杂度的下界与上界。这里不再深入因为 Big O 是描述一般算法时间复杂度最常用的记号。为什么用 Big O最坏情况理解了三种记号之后选择最坏情况来衡量算法效率的理由就清楚了用最坏情况能确保算法在所有结果下都可扩展。如果一个算法可能以常数时间运行、但最坏情况下是线性时间那么只有最坏情况也能扛住它才能随输入增长而扩展。你必须确信当输入突然从 10 个变成一百万个时代码不会卡死、不会让用户干等。相同复杂度的算法为什么常数会被丢弃两个算法复杂度相同就代表它们一样好吗课程用两个代码示例回答这个问题。第一个是我们已经见过的odd_numbers时间复杂度 O(N)def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 1 end end第二个改动很小——每次递增 2def odd_numbers(max_number) current_number 1 while current_number max_number if current_number % 2 ! 0 puts current_number end current_number 2 end end对输入 n第二个版本每次迭代跳过 2步骤数约为原来的一半可以写成 O(N/2)。但正如前面所说Big O 追求的不是精确时间而是时间随输入规模增长的关系。Big O 不关心常数因为常数与算法随输入如何扩展无关——如果要在 O(N/2 5N) 与 O(N 5/2N) 之间比较那既不有趣也不方便。因此两个算法的 Big O 效率都是 O(N)它们随输入增长的比例速率相同。换个角度看常数最终会变得无关紧要。看下面的对比O(10N) 与 O(n²)NO(10N)O(n²)差距1101—55025—1001,00010,00010 倍1,00010,0001,000,000100 倍10,000100,000100,000,0001,000 倍所以当 N 达到 100 时O(10N) 快于 O(n²)。但从实践角度看对某些很小的输入集合n² 算法反而可能比 N 算法更快见上表前两行。这也提醒你在保证时间复杂度正确的前提下尽量让代码本身写得高效例如减少不必要的变量和遍历。复杂度分析在课程后续章节中的落地时间复杂度分析不是孤立的理论它贯穿整个计算机科学模块哈希表Hash Maphash_map_data_structure.md 一课明确给出哈希表的插入、检索、删除平均复杂度为 O(1)因为操作直接基于数组索引最坏情况为 O(n)发生在所有数据哈希到同一个桶、需要遍历链表时。这正解释了为什么课程强调设计良好的哈希函数以减少冲突。二叉搜索树BSTproject_binary_search_trees.md 指出 BST 的插入/删除可达到 O(log n)并专门提醒不要用原始输入数组实现这些操作否则会丢掉这一性能优势——这正是把本课的 O(log N) 分析应用于实际项目的实例。递归与分治recursive_methods.md 与 project_recursion.md 中的归并排序是 O(N log N) 的经典实现而递归深度过大会导致调用栈溢出——这既是时间复杂度的延伸也涉及空间复杂度。数据结构的权衡common_data_structures_algorithms.md 一课讨论栈、队列、链表以及 BFS/DFS 搜索算法时处处以操作耗时与内存占用的权衡为出发点project_linked_lists.md 中的链表操作at(index)需要从头遍历正是线性复杂度的实战案例。空间复杂度时间与空间是一体两面space_complexity.md 用与时间相同的 Big O 记号衡量内存使用并引入了辅助空间分析auxiliary space analysis的概念。知识自测回顾本课的核心问题检验自己是否掌握什么是 Big O它衡量的效率维度是什么最常见的 Big O 记号有哪些从快到慢如何排列为什么要使用 Big O最坏情况来衡量算法什么是 Big Omega为什么它没那么有用为什么 Big O 中常数不影响复杂度结论为什么不能用实际运行时间衡量算法效率O(log N) 算法在数据翻倍时步骤数如何变化此外课程的作业环节还推荐了外部资源包括面向 Ruby 开发者的 Big-O 指南、Big-O 速查表含各常见数据结构操作与排序算法的时间/空间复杂度对照以及更深入的 Ruby 时间复杂度专题文章可作为进阶阅读在完成本课后自行查阅。下一课将把同样的分析框架应用到空间维度请继续学习 space_complexity.md。【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考