DSA 时间复杂度
运行时间
为了完全理解算法，我们必须了解如何评估算法完成任务所需的时间，即运行时间。
探索算法的运行时间很重要，因为使用效率低下的算法可能会使我们的程序变慢，甚至无法运行。
通过了解算法运行时间，我们可以为自己的需求选择正确的算法，并使我们的程序运行更快，并有效地处理大量数据。
实际运行时间
在考虑不同算法的运行时间时，我们**不会**查看已实现算法的实际运行时间，原因如下。
如果我们在编程语言中实现一个算法，并运行该程序，它使用的实际时间取决于许多因素
- 用于实现算法的编程语言
- 程序员如何为算法编写程序
- 用于使已实现算法能够运行的编译器或解释器
- 运行算法的计算机上的硬件
- 计算机上的操作系统和其他正在运行的任务
- 算法正在处理的数据量
由于所有这些不同的因素都在算法的实际运行时间中发挥作用，我们如何才能知道一个算法是否比另一个算法更快？我们需要找到一个更好的运行时间度量。
时间复杂度
为了评估和比较不同的算法，与其查看算法的实际运行时间，不如使用时间复杂度。
时间复杂度比实际运行时间更抽象，并且不考虑编程语言或硬件等因素。
时间复杂度是在大量数据上运行算法所需的运算次数。运算次数可以被视为时间，因为计算机对每个运算都需要一些时间。
例如，在寻找数组中最小值的算法中，必须比较数组中的每个值一次。每个这样的比较都可以被视为一个运算，每个运算都需要一定的时间。因此，算法找到最小值所需的时间取决于数组中值的个数。
因此，找到最小值所需的时间与值的个数呈线性关系。100 个值会导致 100 次比较，而 5000 个值会导致 5000 次比较。
时间和数组中值的个数之间的关系是线性的，可以用类似这样的图表来显示
"一次运算"
在谈到这里的“运算”时，“一次运算”可能需要一个或多个 CPU 周期，它实际上只是一个帮助我们进行抽象的词语，以便我们能够理解时间复杂度是什么，以及如何找到不同算法的时间复杂度。
算法中的一次运算可以被理解为我们在算法的每次迭代中，或者对每块数据执行一次，并且花费固定时间的操作。
例如：比较两个数组元素，如果一个比另一个大就交换它们，就像冒泡排序算法所做的那样，可以被理解为一次运算。将此理解为一次、两次或三次运算实际上不会影响冒泡排序的时间复杂度，因为它花费固定时间。
我们说一个运算花费“固定时间”，如果它花费的时间与算法正在处理的数据量 (\(n\)) 无关。比较两个特定的数组元素，如果一个比另一个大就交换它们，无论数组包含 10 个还是 1000 个元素，花费的时间都是一样的。
大 O 符号
在数学中，大 O 符号用于描述函数的上界。
在计算机科学中，大 O 符号更具体地用于找到算法的最坏情况时间复杂度。
大 O 符号使用一个大写字母 O 带有括号 \(O() \)，括号内有一个表示算法运行时间的表达式。运行时间通常用 \(n\) 表示，它是算法正在处理的数据集中值的个数。
以下是一些不同算法的大 O 符号示例，仅供参考
| 时间复杂度 | 算法 |
|---|---|
| \[ O(1) \] | 例如，在数组中查找特定元素 |
| \[ O(n) \] | 找到最小值。该算法必须在一个包含 \(n\) 个值的数组中执行 \(n\) 次运算才能找到最小值，因为该算法必须比较每个值一次。 |
| \[ O(n^2) \] |
冒泡排序、选择排序 和插入排序 都是具有这种时间复杂度的算法。它们的时间复杂度的原因为解释了这些算法页面的原因。 大型数据集会显着减慢这些算法的速度。仅将 \(n\) 从 100 个值增加到 200 个值，运算次数就会增加多达 30000 次！ |
| \[ O(n \log n) \] | 快速排序算法 的平均速度通常比上面提到的三种排序算法更快，\(O(n \log n)\) 是平均时间，而不是最坏情况时间。快速排序的最坏情况时间也是 \(O(n^2)\)，但它的平均时间使快速排序如此有趣。我们稍后将学习快速排序。 |
当值的个数 \(n\) 增加时，以下是不同算法的时间增加方式
最佳、平均和最坏情况
在解释大 O 符号时，已经提到了“最坏情况”时间复杂度，但算法如何会出现最坏情况呢？
在包含 \(n\) 个值的数组中找到最小值的算法需要 \(n\) 次运算才能完成，并且始终如此。因此，该算法具有相同的最佳、平均和最坏情况。
但对于我们将要研究的许多其他算法，如果我们保持值的个数 \(n\) 不变，运行时间仍然会根据实际值发生很大变化。
不用说太多细节，我们可以理解，排序算法的运行时间可能会不同，具体取决于它正在排序的值。
假设你必须手动将 20 个值从最小值到最大值排序
8, 16, 19, 15, 2, 17, 4, 11, 6, 1, 7, 13, 5, 3, 9, 12, 14, 20, 18, 10
这将需要你几秒钟才能完成。
现在，假设你必须排序 20 个值，这些值几乎已经排好序了
1, 2, 3, 4, 5, 20, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
你可以非常快地排序这些值，只需将 20 移到列表的末尾即可完成，对吧？
算法的工作原理类似：对于相同数量的数据，它们有时可能很慢，有时可能很快。因此，为了比较不同算法的时间复杂度，我们通常使用大 O 符号来查看最坏情况。
大 O 符号的数学解释
根据你在数学方面的背景，本节可能难以理解。它的目的是为那些需要更深入了解大 O 符号的人创建一个更扎实的数学基础。
如果你现在不理解，别担心，你可以稍后再回来。如果这里的数学对你来说太难了，也不要太担心，你仍然可以享受本教程中的不同算法，学习如何编程它们，并了解它们的快慢程度。
在数学中，大 O 符号用于为函数创建上限，而在计算机科学中，大 O 符号用于描述当数据值数量 \(n\) 增加时算法运行时间如何增加。
例如，考虑函数
\[f(n) = 0.5n^3 -0.75n^2+1 \]
函数 \(f\) 的图形如下所示
再考虑另一个函数
\[g(n) = n^3 \]
我们可以像这样绘制它
使用大 O 符号，我们可以说 \(O(g(n))\) 是 \(f(n)\) 的上限，因为我们可以选择一个常数 \(C\)，使得 \(C \cdot g(n)>f(n)\)，只要 \(n\) 足够大。
好的，让我们试试。我们选择 \(C=0.75\)，这样 \(C \cdot g(n) = 0.75 \cdot n^3\)。
现在让我们在同一个图中绘制 \(0.75 \cdot g(n)\) 和 \(f(n)\)
我们可以看到 \(O(g(n))=O(n^3)\) 是 \(f(n)\) 的上限，因为 \(0.75 \cdot g(n) > f(n)\) 对于所有大于 1 的 \(n\)。
在上面的例子中，\(n\) 必须大于 1 才能使 \(O(n^3)\) 成为上限。我们称这个极限为 \(n_0\)。
定义
令 \(f(n)\) 和 \(g(n)\) 为两个函数。我们说 \(f(n)\) 是 \(O(g(n))\) 当且仅当存在正常数 \(C\) 和 \(n_0\)，使得
\[ C \cdot g(n) > f(n) \]
对于所有 \(n>n_0\)。
在评估算法的时间复杂度时，\(O()\) 仅对大量的值 \(n\) 成立是可以的，因为这是时间复杂度变得重要的时刻。换句话说：如果我们要排序 10、20 或 100 个值，那么算法的时间复杂度并不那么有趣，因为计算机无论如何都会在很短的时间内对这些值进行排序。
