我想知道，如果我估计了最坏情况的时间复杂度，我如何估计我的程序在我的机器（例如 2.5 Ghz 机器）上执行的时间？ 例如： - 如果我有一个 O(n^2) 的程序，在最坏的情况下，并且 n<100000，我怎么能知道 /estimate 在编写实际的程序/过程之前，它需要执行的时间秒？
知道一个程序的实际执行情况不是很好吗，而且它还可以节省编写代码，最终证明是低效的！非常感谢帮助。
问问题
2996 次
3 回答
4
由于大 O 复杂度忽略了线性系数和较小的项，因此仅考虑其大 O 复杂度是不可能估计算法的性能的。
事实上，对于任何特定的 N，您无法预测两种给定算法中的哪一种会执行得更快。
例如，O(N) 并不总是比 O(N*N) 快，因为对于许多小的 N 值，采用 100000000*n 步的算法是 O(N) 比采用 N*N 步的算法慢。
这些线性系数和渐近较小的项因平台而异，甚至在相同等价类的算法中也不同（就大 O 度量而言）。3
您尝试使用大 O 表示法的问题不是它旨在解决的问题。
于 2013-02-12T21:34:13.487 回答
0
而不是处理复杂性，您可能想看看Worst Case Execution Time（WCET）。这个研究领域很可能与您正在寻找的内容相对应。
于 2013-02-12T21:56:30.123 回答
-1
将 N^2 乘以您在最内层循环的迭代中花费的时间，并且您有一个大概的估计。
于 2013-02-12T16:39:21.630 回答