算法分析 | 第一套（渐近分析）

为什么要进行性能分析？

有很多重要的事情应该注意，比如用户友好性、模块化、安全性、可维护性等。 为什么要担心性能？

答案很简单，只有我们有性能，我们才能拥有上述所有东西。所以性能就像货币，我们可以通过它购买上述所有东西。

总而言之，性能 == 规模。想象一个可以加载 1000 页的文本编辑器，但每分钟可以拼写检查 1 页，或者一个需要 1 小时将图像向左旋转 90 度的图像编辑器。如果一个软件功能不能应付用户需要执行的任务的规模，那它就像挂了一样。

给定一个任务的两种算法，我们如何找出哪个更好？

一种比较天真的方法是：实现这两种算法并在您的计算机上针对不同的输入运行这两个程序，然后看看哪一个花费的时间更少。这种用于分析算法的方法存在许多问题。

1. 对于某些输入，第一种算法的性能可能优于第二种算法。对于某些输入，第二个表现更好。

2. 也有可能对于某些输入，第一种算法在一台机器上表现更好，而第二种算法在其他机器上对其他一些输入效果更好。

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

例如，让我们考虑排序数组中的搜索问题（搜索给定项目）。一种搜索方式是线性搜索（增长顺序是线性的），另一种方式是二分搜索（增长顺序是对数）。

为了理解渐近分析如何解决上述分析算法中的问题，假设我们在快速计算机A上运行线性搜索，在慢速计算机B上运行二进制搜索，我们为两台计算机选择常数值，以便它准确地告诉我们给定机器在几秒钟内执行搜索所需的时间。假设A的常数是 0.2，B的常数是 1000，这意味着 A 比 B 强大 5000 倍。对于输入数组大小 n 的小值，快速计算机可能需要更少的时间。但是，在输入数组大小达到某个值后，与线性搜索相比，二分搜索肯定会开始花费更少的时间，即使二分搜索是在慢速机器上运行的。原因是二分搜索相对于输入大小的增长顺序是对数的，而线性搜索的增长顺序是线性的。因此，在输入大小的某个值之后，始终可以忽略与机器相关的常量。

以下是此示例的一些运行时间：

A 上的线性搜索运行时间（以秒为单位） ：0.2 * n

B 上的二进制搜索运行时间（以秒为单位） ：1000*log(n)

------------------------------------------------
|n      | Running time on A | Running time on B |
-------------------------------------------------
|10     | 2 sec             | ~ 1 h             |
-------------------------------------------------
|100    | 20 sec            | ~ 1.8 h           |
-------------------------------------------------
|10^6   | ~ 55.5 h          | ~ 5.5 h           |
-------------------------------------------------
|10^9   | ~ 6.3 years       | ~ 8.3 h           |
-------------------------------------------------

渐近分析总是有效吗？

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

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

以上就是本篇文章的全部内容

我真的希望你能从这篇文章中得到一些有用的东西。这里汇总了我的全部原创及作品源码：GitHub 如果大家能给我的 Github 存储库上添一些星星就更好了😊。

我已经写了很长一段时间的技术博客，这是我的一篇 算法分析 | 第一套（渐近分析）。我乐于通过文章分享技术与快乐。您可以访问我的华为云博客主页： 华为云-海拥、个人博客：haiyong.site 以了解更多信息。希望你们会喜欢！

💌 欢迎大家在评论区提出意见和建议！💌

如果你真的从这篇文章中学到了一些新东西，喜欢它，收藏它并与你的小伙伴分享。🤗最后，不要忘了❤或📑支持一下哦。

下一篇——算法分析 | 第二套（最差、平均和最佳情况）