algorithm - 来自公式的大 o 符号

Question

当您有这样的公式时:3n² + 10n.log(n) + 1000n + 4.log(n) + 9999。

你会为 big-o-notation 选择增长最快的函数吗？在这种情况下，n² 的大 O。

谁能帮我理解这是在问什么？假设您有一台计算机需要 1 分钟 来解决大小为 n = 1,000 的问题实例。假设您购买了一台运行速度比旧计算机快 1,000 倍 的新计算机。假设我们的算法的时间复杂度为 T(n)，1 分钟内可以运行多少实例大小？

• T(n) = n
• T(n) = n³
• T(n) = 10n

Answer 1

假设 T(n) 是执行 n 个操作 (op) 所需的时间。

我们知道旧机器中的 T(1000) = 1'，新机器中的 T(1000) = 1'/1000(因为新机器快 1000。)

a) T(n) = n

这意味着在旧机器中 1' 有 1000 个运算。在新机器中(快 1000 倍)是 1'/1000 中的 1000 次运算。所以 1000000 op in 1' 在新机器中，答案是 100 万。换句话说，新机器将在 1' 内计算 1000000 次操作(这是每分钟操作数的 1000 倍。)

b) T(n) = n^3

在这里，我们在 1'(旧机器)中有 1000^3 个运算，在 1'/1000(新机器)中有 1000^3 个运算。因此，在新机器中:1000^3 1000 op in 1'，或 1000^3 10^3 op in 1'，即 10000^3 op in 1'，答案是一万。

c) T(n) = 10n

我们在 1'(旧)中有 10 * 1000 个运算，在 1'/1000(新)中有 10 * 1000 个运算。所以，1' 中有 10 * 1000000 次运算，答案还是 100 万。

正如我们所见，T(n) = n 和 T(n) = 10 n 的答案是相同的。事实上，无论 C > 0 的值如何，它们也等于 T(n) = C n 的答案。要看到这一点，我们只需将上面的 C 替换为 10:

C 1000 op in 1'(旧)，C 1000 op in 1'/1000(新)或 C 1000000 in 1'，答案是 1000000。

这就是为什么我们谈论 O(n)、O(n^2)、O(n^3) 等，而不管 O 中隐藏的常量。