algorithm - 根据输入大小找出算法中的时间步数

Question

假设您运行输入大小为 1000 的 O(log n) 算法，并且该算法需要 110 次操作。当您将输入大小加倍至 2000 时，该算法现在需要 120 次操作。当您再次将输入大小翻倍至 4000 时，您对所需操作数的最佳猜测是多少？

Answer 1

Big-O 表示法用于指示算法在最坏情况下相对于输入大小的运行时间。它不会预测任何有关实际操作数量的信息。它没有考虑低阶项和常数因子。

Answer 2

There's an additive constant, corresponding to run-time overhead, in the solution. The following presumes that the result is Ɵ(log n) rather than just O(log n).

You could go on and explicitly solve for the constants if you wanted to make generalized predictions, but doing so based on two points would be pretty dubious.

Answer 3

让我们f(n)估计操作次数，只需将您的问题放入等式：

f(n) = c * log(n) // O(log n) algorithm
f(1000) = 110
f(2000) = 120
f(4000) = ?

找到c，你就会找到答案。但当然，这只是基于给定数据和限制行为的最佳猜测f估计。

由于多种原因，这不会是一个准确的预测：

• 大 O 符号只给出了算法复杂度的限制行为，而不是实际的复杂度公式。
• 操作的数量可能很大程度上取决于数据的性质，而不仅仅是多样性n。
• 限制行为是在可能数据的特定情况下计算的（通常是最坏的情况）。