algorithm - 算法的效率

Question

我是一名计算机科学专业的学生，​​我是算法的新手。我们在类里面学习算法设计与分析类(class)。我想知道为什么算法的时间复杂度是根据O(n)、O(log n) 等而不是以秒或毫秒为单位衡量实际时间？

Answer 1

为什么没有用秒/毫秒的实际时间来描述效率？

我们不这样做的原因有很多(其中一些是显而易见的):

• 实际时间因算法的实现而异。
• 实际时间因编译器生成的代码(以及指定的所有优化选项)而异
• 实际时间因分时、通信开销(在分布式算法中)等原因而有所不同。
• 实际时间因运行程序的系统配置(时钟速率、缓存大小、网络拓扑等)而异。
• 我们还想了解算法如何随着问题的规模进行扩展。描述算法相对于问题大小的速度有多快的函数更有用。

为什么效率没有被描述为输入大小的精确函数，而它给出了准确的运行时间？

• 再次，系统配置(系统架构、时钟速率、指令集等)
• 同样，编译器对代码的优化可能会改变一些系数。
• 对于复杂算法或确切运行时间取决于输出的某些特征的算法，推导精确公式可能并不容易。

然后呢？

这就是为什么它被描述为属于一类函数。

这样做的好处是我们知道算法的可扩展性(相对于输入大小)，而无需深入了解实现或实际系统的细节。我们甚至可以描述一类算法的最佳/最差时间复杂度(例如 Omega(n log n) 用于基于比较的排序算法)。

这样做的缺点是常量被隐藏了，只保留最强大的项。 2 个算法可能具有相同的时间复杂度，但一个可能比另一个更快，因为它具有更小的常数(Floyd Cycle Finding Algorithm vs. Brent Cycle Finding Algorithm)。一些具有巨大隐藏常数的算法只有在输入量非常大时才有用。因此，不应仅根据时间复杂度来选择算法，还需要考虑最大可接受的输入大小。