c - 实证运行时分析

Question

嘿，所以我很难掌握实证运行时分析。所以我有这个问题:

假设我们有一个复杂度为 O(1) 的函数，执行时间为 8 秒，n = 2,000。如果 n = 10,000，您期望运行时间是多少？

现在这是我认为错误的思考过程: 如果 T(n) 是 O(1) 那么 T(n) = c * O(1) 其中 c 只是某个常数。所以求解 c 我们得到 c = T(n)/O(1)。现在，因为我们知道 T(2000) = 8s 和 n = 2000，我们可以将其插入以求解 c，c = (8s)/(2000) 得到 0.004。 现在我们必须对 n = 10,000 做同样的事情，所以在这种情况下 T(10,000)= c * O(1) 在这种情况下，我们可以只插入我们之前发现的相同的 c，因为它只是一个常数，并为 O(1) 插入 10,000，这将得到 T(10,000) = (0.004) * 10,000，等于 40s。我只是不确定我的思考过程是否正确。

Answer 1

正确的答案是我们不能期待任何特定的时间。

说一个函数的运行时间 O(1) 就是说有一些数字 C 使得该函数总是在小于 C 秒的时间内运行。如果函数在 8 秒内运行一次，我们知道 C 至少为 8。但它可能是一百万。或者 septillion。

O(1) 确实告诉我们，无论 n 是多少，运行时间都是有限的。该运行时间可以随着 n 的不同而上下变化，但它始终受 C 的限制。

相比之下，将其与运行时间为 O(n) 的函数进行比较。这意味着有一个数字 C 使得函数的运行时间总是小于 C*n 秒(除了允许有限数量的异常)。所以我们没有固定的限制；我们有一个取决于 n 的限制。随着 n 的增长，此函数可能需要越来越多的时间。

也可能不是。 O 表示法仅告诉您函数运行时间的限制。它不会告诉您实际的运行时间。如果我知道你昨天在你的车里加了一加仑汽油，你走了 30 英里，我知道你的车每加仑至少可以跑 30 英里。如果你今天加两加仑汽油，我知道你至少可以跑 60 英里，但也许你可以跑更多，但我不知道你实际能跑多远。我知道你的旅行有限制，但我不知道它到底是什么，也不知道你会走多远。