2

我是一名计算机科学专业的学生，​​我对算法不熟悉。我们正在课堂上学习算法设计与分析课程。我想知道为什么算法的时间复杂度是用等来衡量的 O(n)，O(log n)而不是用秒或毫秒来衡量实际时间？

4

4 回答 4

3

为什么效率不是以秒/毫秒为单位的实际时间来描述的？

我们不这样做的原因有很多（其中一些是显而易见的）：

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

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

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

然后？

这就是为什么它被描述为属于一类功能。

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

这样做的缺点是常数是隐藏的，只剩下最强大的项。2 算法可能具有相同的时间复杂度，但一个可能比另一种更快，因为它具有较小的常数（弗洛伊德循环查找算法与布伦特循环查找算法）。一些具有巨大隐藏常数的算法只有在输入非常大时才会有用。因此，不应仅根据时间复杂度来选择算法，还需要考虑最大可接受的输入大小。

于 2013-02-21T10:00:46.027 回答
3

渐近计算复杂度对于讨论算法的理论方面很有用。不讨论实际执行时间的主要原因是：

  • 实际执行时间因硬件、输入大小和优化而有很大差异。
  • 它使我们能够讨论和分析具有高（甚至无限）执行时间的算法。
  • 给定足够长的输入，类分类，也称为 Big-O 表示法，无论其实现如何，都为我们提供了对算法效率的有用描述。例如，对于足够长的输入，O(log(n))算法比O(n)算法快，但对于较短的输入，后者可能更快。
  • 讨论与语言无关，适用于任何软件架构。

应始终考虑实际考虑，但 Big-O 是每次讨论算法解决方案的基础。如果您不能 Big-O 分析您的算法，您的代码将永远无法扩展。

于 2013-02-21T09:37:29.717 回答
2

执行单个指令的时间取决于硬件，并且由于算法是人为的，因此最好以特定格式返回答案。Big O 定义最坏情况 N 代表块代码将执行的次数，其中 n 通常定义数组对象的元素数。

于 2013-02-21T09:40:34.393 回答
1

需要意识到的关键是，这些复杂性类并非旨在描述算法的实际执行时间，而是描述最坏情况下的执行时间。

这很重要，因为一个递归算法，并且具有复杂度等级 O(2^N) 可以执行等效于 O(1) 如果由于传递了一个参数，它实际上不必执行递归，但是Big-O 表示法您没有描述算法的特定执行 - 再次，您描述的是算法的最坏情况执行。

执行时间毫秒测量测量的是不同的东西。Big-O 表示法描述了上述算法的最坏情况，但它的执行方式并不特定于它所运行的特定平台，而毫秒时间测量只能描述单个特定机器上的单个特定执行. 在您的普通桌面系统上，特别是如果您在 C# .NET 或 Java 等托管语言上构建，每次运行算法时都会出现波动，例如垃圾收集 - 测量函数执行所需的时间前一刻可能给出 3 毫秒，下一分钟可能给出 5 毫秒。在速度更快的计算机上，它可能只需要 0.005 毫秒 - 如您所见，

于 2013-02-21T09:50:42.953 回答