原文：
www.kdnuggets.com/2020/06/time-complexity-measure-efficiency-algorithms.html
评论
作者：Diego Lopez Yse，数据科学家
照片由 Icons8 Team 在 Unsplash 提供
在计算机编程中，和生活的其他方面一样，解决问题的方法各不相同。这些不同的方法可能意味着不同的时间、计算能力或你选择的其他度量标准，因此我们需要比较不同方法的效率，以选择合适的方法。
现在，正如你可能知道的那样，计算机能够根据算法解决问题。
算法是告诉计算机该做什么和怎么做的过程或指令（步骤集合）。
如今，它们发展得如此迅速，即使是在完成相同任务的情况下也可能有很大不同。在最极端的情况下（顺便说一句，这种情况很常见），用不同编程语言编写的不同算法可能会指示不同硬件和操作系统的计算机以完全不同的方式执行相同任务。这真疯狂，不是吗？
问题是，当一个算法花费几秒钟完成时，另一个算法即使在处理小数据集时也会花费几分钟。我们如何比较不同的性能并选择最佳算法来解决特定问题？
幸运的是，我们有方法可以做到这一点，我们不需要等待算法运行才能知道它是否能够快速完成任务，或者它是否会因输入的重量而崩溃。当我们考虑算法的复杂度时，我们不必关心执行的确切操作次数；我们应该关心操作次数与问题规模的关系。想想看：如果问题规模翻倍，操作次数是否保持不变？是否也翻倍？是否以其他方式增加？要回答这些问题，我们需要测量算法的时间复杂度。
时间复杂度表示语句执行的次数。算法的时间复杂度不是执行特定代码所需的实际时间，因为这取决于其他因素，如编程语言、操作软件、处理能力等。时间复杂度的核心思想是，它只能以一种仅依赖于算法本身及其输入的方式来衡量算法的执行时间。
为了表示算法的时间复杂度，我们使用一种叫做*“大 O 记号”*的东西。**大 O 记号是我们用来描述算法时间复杂度的语言。**它帮助我们比较不同解决问题的方法的效率，并帮助我们做出决策。
大 O 记号表示算法的运行时间相对于输入增长的速度（这个输入被称为“n”）。这样，如果我们说一个算法的运行时间按“输入大小的顺序”增长，我们会表示为“O(n)”。如果我们说一个算法的运行时间按“输入大小的平方的顺序”增长，我们会表示为“O(n²)”。但这到底是什么意思呢？
理解时间复杂度的关键是理解事物增长的速度。这里讨论的速率是每个输入大小所花费的时间。时间复杂度有不同类型，让我们来检查最基本的几种。
当时间复杂度是常量（记作“O(1)”）时，输入的大小（n）无关紧要。具有常量时间复杂度的算法运行所需时间固定，与 n 的大小无关。它们的运行时间不会因输入数据而改变，这使它们成为最快的算法。
常量时间复杂度
例如，如果你想知道一个数字是奇数还是偶数，你会使用一个具有常量时间复杂度的算法。无论数字是 1 还是 90 亿（输入“n”），该算法只会执行相同的操作一次，并给出结果。
同样，如果你想打印一句像经典的“Hello World”这样的短语，你也会使用常量时间复杂度，因为操作次数（在这种情况下是 1）将保持不变，无论你使用什么操作系统或机器配置。
为保持常量，这些算法不应包含循环、递归或调用任何其他非常量时间函数。对于常量时间算法，运行时间不会增加：量级始终为 1。
当时间复杂度与输入大小成正比增长时，你面临的是线性时间复杂度，或 O(n)。具有这种时间复杂度的算法会以“n”次操作处理输入（n）。这意味着随着输入的增长，算法完成所需的时间也会成比例增加。
线性时间复杂度
这些情况是你需要查看列表中的每个项来完成任务（例如，找出最大值或最小值）。或者你也可以考虑像读书或在 CD 堆中寻找一张 CD（记得吗？）这样的日常任务：如果所有数据都必须检查，输入数据越大，操作次数就越多。
线性运行时间的算法非常常见，它们与算法访问输入中的每个元素有关。
具有这种复杂度的算法使计算变得非常快速。如果一个算法的执行时间与输入大小的对数成正比，则称该算法在对数时间内运行。这意味着，与每个后续步骤所需的时间增加相反，时间以与输入“n”成反比的数量级减少。
对数时间复杂度
它的秘诀是什么？这种类型的算法从不需要遍历所有输入，因为它们通常通过每一步丢弃大量未检查的输入来工作。这种时间复杂度通常与每次将问题对半分割的算法相关，这是一种被称为“分而治之”的概念。分而治之算法通过以下步骤解决问题：
-
他们将给定问题分解为相同类型的子问题。
-
他们递归地解决这些子问题。
-
他们适当地结合子答案以回答给定的问题。
考虑这个例子：假设你想在一个按字母顺序排列的字典中查找一个词。有至少两种算法可以做到这一点：
算法 A：
- 从书的开头开始，按照顺序查找，直到找到你要找的联系人。
算法 B：
-
从书的中间打开并检查第一页上的第一个词。
-
如果你要找的词在字母顺序上更大，则查找右半部分。否则，查找左半部分。
哪一种更快？算法 A 按字逐个处理 O(n)，而算法 B 在每次迭代中将问题分成两半 O(log n)，以更高效的方式达到相同的结果。
对数时间算法（O(log n)）是仅次于常数时间算法（O(1)）的第二快算法。
在这种类型的算法中，运行时间直接与输入大小的平方成正比（类似于线性，但平方）。
在大多数场景中，特别是对于大型数据集，具有二次时间复杂度的算法需要很长时间才能执行，应该避免使用。
二次时间复杂度
嵌套For 循环的运行时间是二次的，因为你在另一个线性操作中运行一个线性操作，即nn*，等于n²。
如果你遇到这些类型的算法，你要么需要大量的资源和时间，要么需要想出一个更好的算法。
在指数时间算法中，增长率随着输入（n）的每次增加而翻倍，通常会遍历所有输入元素的子集。每当输入单元增加 1 时，都会使你执行的操作数量翻倍。这听起来不太好，对吧？
这种时间复杂度的算法通常在你对最佳解决方案了解不多的情况下使用，你必须尝试所有可能的数据组合或排列。
指数时间复杂度
指数时间复杂度通常出现在暴力算法中。这些算法盲目地遍历整个可能解决方案的领域，以寻找一个或多个满足条件的解决方案。它们通过简单地尝试每一个可能的解决方案直到找到正确的来找到解决方案。这显然不是一种优化的任务执行方式，因为它会影响时间复杂度。暴力算法在密码学中作为攻击方法使用，通过尝试随机字符串来破解密码保护，直到找到正确的密码来解锁系统。
与二次时间复杂度一样，你应该避免使用具有指数运行时间的算法，因为它们扩展性差。
一般来说，我们发现算法的操作越少，它的速度越快。这看起来是个好原则，但我们如何将它应用到现实中呢？
如果我们有一个算法（不论是什么），我们怎么知道它的时间复杂度呢？
在某些情况下，这可能相对简单。假设你有一个外部For 循环，它遍历输入列表中的所有项，然后是一个嵌套的内部For 循环，它再次遍历输入列表中的所有项。执行的总步骤数是 n * n，其中 n 是输入数组中的项数。
但是，你如何找出复杂函数的时间复杂度呢？
为了找到答案，我们需要将算法代码拆解成各个部分，并尝试找出各个部分的复杂度。是的，抱歉告诉你，但并没有一个按钮可以告诉你算法的时间复杂度。你必须自己去做。
主要时间复杂度
**作为经验法则，最好尽量保持你的函数运行在线性时间复杂度范围内，**但显然这并不总是可能的。
有不同的大 O 记法，例如*“最佳情况”、“平均情况”和“最差情况”*，但真正重要的是最差情况；这些情况是可能严重崩溃一切的。它们直接触及时间复杂度为何重要，并指出为何一些算法在不花费几亿年时间的情况下根本无法解决问题。
最坏情况分析 给出了执行算法时必须执行的基本操作的最大数量。它假设输入处于最糟糕的状态，并且需要做最大量的工作以纠正问题。例如，对于一个旨在将数组按升序排序的排序算法，当输入数组按降序排列时，最坏的情况就会发生。在这种情况下，必须进行最多的基本操作（比较和赋值）以将数组设置为升序。这样想：如果你必须通过阅读每个名字来在目录中搜索一个名字，直到找到正确的那个，最坏的情况是你想要的名字是目录中的最后一个条目。
总结一下，算法的时间复杂度越低，实际工作中算法执行得越快。 在设计或管理算法时，你应该考虑这一点，并意识到它可能会对算法的实用性或完全无用性产生巨大差异。
对这些主题感兴趣？请在 Linkedin 或 Twitter 上关注我
个人简介：Diego Lopez Yse 是一位经验丰富的专业人士，拥有在不同领域（资本市场、生物技术、软件、咨询、政府、农业）获得的坚实国际背景。始终是团队的一员。擅长商业管理、分析、金融、风险、项目管理和商业运营。拥有数据科学和企业金融硕士学位。
原文。经许可转载。
相关：
-
人人都能用的 Python：免费电子书
-
使用 5 种机器学习算法分类稀有事件
-
数据科学家的编码习惯
1. 谷歌网络安全证书 - 快速进入网络安全领域的职业轨道。
2. 谷歌数据分析专业证书 - 提升你的数据分析能力
3. 谷歌 IT 支持专业证书 - 支持你的组织 IT