performance - 当看似常数确实会影响复杂性时，我如何确定算法的时间复杂度，而当我被教导其他方式时？

Question

举个例子：Wolfram|Alpha

如果我有 n*(lgn) / lg(lg(n))

比较

5000n

无论 n 有多高，5000n 总是会更高。但是，如果我去掉常数，则相反。但我一直认为，在事物的宏大方案中忽略了常数相乘（5000n 将被视为 n），这将导致 5000n 被认为更小，而它似乎更大。

当被问及哪些时间复杂度更差的算法时，我该如何回答？

Answer 1

需要记住的是，当人们比较复杂度时，他们几乎总是考虑渐近复杂度，也就是说，随着n变得越来越大，它越大。

在这种情况下，尽管5000n > n*log n/ log log n对于 的任何合理值n，后者仍然具有更高的复杂性。

插上电源5000 < log n/ log log n让我得到了答案n = 2*10^23683（点击“近似形式”），果然，5000n < n*log n/ log log n对于n = 2*10^23683.

Answer 2

在渐近复杂性分析中故意忽略常数乘数。对于算法的分析，抽象地说，很难计算它们——它们取决于随时间变化的计算机行为的实际方面。

对于选择算法，渐近复杂度只是要考虑的一种衡量标准。估计或测量预期问题规模的实际时间也很重要。如果随着问题大小的增加算法将变得非常慢，渐近复杂度会发出警告。