<分区>
所以根据我的理解，我们只能用渐近分析来评估算法，但在执行算法时，它只能返回时间量。 我的问题是我们如何比较这两者？
标签 algorithm
<分区>
所以根据我的理解，我们只能用渐近分析来评估算法，但在执行算法时，它只能返回时间量。 我的问题是我们如何比较这两者？
最佳答案
它们具有可比性，但不是您想要的方式。
如果您有一个渐近评估为 O(N^2) 的实现，并且您测量为在输入 N=1000 时运行 60 秒，那么如果您将输入更改为 N=2000，我会期望运行时间大约为 60*(2^2) 4 分钟(我将输入增加了两倍，运行时间增加了 2 平方倍)。
现在，如果您有另一个算法也是 O(N^2)，您可以观察到它在 10 秒内运行 N=1000(编译器创建更快的指令，或者 CPU 更好)。现在，当您移动到 N=2000 时，我预计运行时间约为 40 秒(相同的逻辑)。如果您实际测量它，由于系统负载或优化，您可能仍会发现与预期值存在一些差异，但随着 N 的增长，它们变得不那么明显了。
因此，您无法真正仅根据渐近复杂度来判断哪种算法会更快。渐近复杂度保证输入足够大，而较低的复杂度会更快，但没有保证“足够大”意味着什么。
另一个例子是搜索。您可以进行线性搜索 O(N) 或二分搜索 O(logN)。如果您的输入很小(<128 整数)，编译器和处理器使线性搜索比二进制搜索更快。然而，将 N 增加到 100 万个项目，二分搜索将比线性搜索快得多。
通常，对于大输入首先优化复杂性，对于小输入首先优化运行时间。一如既往，如果您关心性能，请执行基准测试。
关于algorithm - 我们如何比较理论和实践中的执行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48655478/