算法复杂性分析中的渐近表示法和分析（基于输入大小）

阳光穿透心脏的1/2处 2023-10-14 07:14 69阅读 0赞

渐近分析被定义为在分析算法中处理上述问题的大思想。在渐近分析中，我们根据输入大小评估算法的性能（我们不测量实际运行时间）。我们计算算法所花费的时间（或空间）如何随着输入大小的增加而增加。

渐近符号是一种根据输入大小描述算法的运行时间或空间复杂度的方法。它通常用于复杂性分析中，用于描述算法随着输入大小的增长而执行的情况。三种最常用的符号是 Big O、Omega 和 Theta。

大 O 表示法 (O)：该表示法提供了算法运行时间或空间使用增长率的上限。它代表最坏的情况，即算法解决问题可能需要的最大时间或空间。例如，如果一个算法的运行时间是O(n)，那么这意味着该算法的运行时间随着输入大小n或更小而线性增加。  
欧米茄表示法 (Ω)：此表示法提供了算法运行时间或空间使用增长率的下限。它代表最好的情况，即算法解决问题可能需要的最小时间或空间。例如，如果一个算法的运行时间为Ω(n)，那么这意味着该算法的运行时间随着输入大小n或更大而线性增加。  
Theta 表示法 (θ)：此表示法提供了算法运行时间或空间使用增长率的上限和下限。它代表平均情况，即算法解决问题通常需要的时间或空间量。例如，如果一个算法的运行时间为 θ(n)，那么这意味着该算法的运行时间随着输入大小 n 线性增加。  
一般来说，渐近符号的选择取决于问题和用于解决问题的具体算法。值得注意的是，渐近符号并不提供算法的精确运行时间或空间使用情况，而是描述算法如何根据输入大小进行缩放。它是一个有用的工具，用于比较不同算法的效率并预测它们在大输入大小上的执行情况。

### 为什么要进行性能分析？ ###

有很多重要的事情需要考虑，比如用户友好性、模块化、安全性、可维护性等。为什么要担心性能呢？答案很简单，只有有性能，我们才能拥有以上所有的东西。所以绩效就像货币一样，我们可以通过它购买以上所有的东西。研究性能的另一个原因是——速度很有趣！总而言之，性能==规模。想象一下，一个文本编辑器可以加载 1000 页，但可以每分钟检查 1 页的拼写，或者一个图像编辑器需要 1 小时才能将图像向左旋转 90 度，或者……你明白了。如果某个软件功能无法应对用户需要执行的任务规模，那么它就等于死了。

### 如何研究算法的效率？ ###

研究算法效率的方法是通过在各种测试输入上运行程序来实现它并进行实验，同时记录每次执行所花费的时间。Java 中的一个简单机制是基于使用 System 类的 currentTimeMillis() 方法来收集此类运行时间。  
该方法报告自称为纪元（UTC 1970 年 1 月 1 日）的基准时间以来经过的毫秒数。关键是，我们是否在执行算法之前记录时间，然后在执行算法之后立即记录时间。

长开始 = System.currentTimeMillis( ); // 记录开始时间  
/*（运行算法）*/  
long end = System.currentTimeMillis( ); // 记录结束时间  
long elapsed = end − start; //经过的总时间

测量经过的时间可以合理地反映算法的效率。

给定一项任务的两种算法，我们如何找出哪一种更好？  
一种简单的方法是——实现这两种算法，并在计算机上针对不同的输入运行这两个程序，看看哪一个花费的时间更少。这种算法分析方法存在很多问题。

对于某些输入，第一个算法的性能可能比第二个更好。对于某些输入，第二个表现更好。  
对于某些输入，第一个算法也可能在一台机器上表现更好，而对于某些其他输入，第二个算法在另一台机器上表现更好。  
渐近分析是解决算法分析中上述问题的重要思想。在渐近分析中，我们根据输入大小评估算法的性能（我们不测量实际运行时间）。我们计算算法所花费的时间（或空间）如何随着输入大小的增加而增加。

例如，让我们考虑排序数组中的搜索问题（搜索给定项目）。

上述搜索问题的解决方案包括：

线性搜索（增长顺序是线性的）  
二分查找（增长顺序是对数）。  
要了解渐近分析如何解决上述分析算法中的问题，

让我们说：  
我们在一台快速计算机 A 上运行线性搜索，并且  
在慢速计算机 B 上进行二分查找  
选择两台计算机的常量值，以便它准确地告诉我们给定计算机执行搜索所需的时间（以秒为单位）。  
假设 A 的常数是 0.2，B 的常数是 1000，这意味着 A 比 B 强大 5000 倍。  
对于较小的输入数组大小 n 的值，快速计算机可能会花费更少的时间。  
但是，在输入数组大小达到一定值之后，即使二分搜索在速度较慢的机器上运行，与线性搜索相比，二分搜索肯定会开始花费更少的时间。  
输入尺寸 A 上的运行时间 B上的运行时间  
10 2秒 〜1小时  
100 20秒 〜1.8小时  
10^6 〜55.5小时 〜5.5小时  
10^9 〜6.3年 〜8.3小时  
原因是二分搜索相对于输入大小的增长顺序是对数的，而线性搜索的增长顺序是线性的。  
因此，在输入大小达到一定值后，与机器相关的常量始终可以被忽略。  
本例的运行时间：

A 上的线性搜索运行时间（以秒为单位）：0.2 \* n  
B 上的二分查找运行时间（以秒为单位）：1000\*log(n)

### 实验分析的挑战： ###

除非在相同的硬件和软件环境中进行实验，否则两种算法的实验运行时间很难直接比较。实验只能在有限的测试输入上进行；因此，他们忽略了实验中未包含的输入的运行时间（这些输入可能很重要）。

为了克服实验分析中的挑战，使用了渐近分析。

### 渐近分析总是有效吗？ ###

渐近分析并不完美，但这是分析算法的最佳方法。例如，假设有两种排序算法在一台机器上分别需要 1000nLogn 和 2nLogn 时间。这两种算法渐近相同（增长阶数为 nLogn）。因此，对于渐近分析，我们无法判断哪一个更好，因为我们忽略了渐近分析中的常数。

此外，在渐近分析中，我们总是谈论大于常数值的输入大小。这些大的输入可能永远不会提供给您的软件，并且渐进较慢的算法对于您的特定情况总是表现更好。因此，您最终可能会选择一种渐近较慢但对您的软件来说较快的算法。

如果您发现任何不正确的内容，或者如果您想分享有关上述主题的更多信息，请发表评论

### 优点或缺点： ###

优点：  
渐近分析提供了对算法如何根据输入大小执行的高级理解。  
它是一个有用的工具，可以比较不同算法的效率并为特定问题选择最佳算法。  
它有助于预测算法在较大输入大小上的执行情况，这对于现实世界的应用程序至关重要。  
渐近分析相对容易执行，只需要基本的数学技能。  
缺点：

渐近分析不提供算法的准确运行时间或空间使用情况。  
它假设输入大小是影响算法性能的唯一因素，但实际情况并非总是如此。  
渐近分析有时可能会产生误导，因为具有相同渐近复杂度的两种算法可能具有不同的实际运行时间或空间使用情况。  
确定算法的最佳渐近复杂度并不总是那么简单，因为时间和空间复杂度之间可能需要权衡。