python - 所有 O(1) 函数的运行时间完全相同。对或错？

Question

“所有 O(1) 函数的运行时间完全相同。” 对或错？任何人都可以向我解释答案吗？

Answer 1

错误的。O(1) 表示恒定时间。这意味着无论输入的大小是多少，函数将在或多或少相同的时间内运行 - 运行时不会随着输入而扩展。

这意味着两个 O(1) 函数都将在恒定时间内运行，尽管它们的常数可能不同。因此，如果您有两个 O(1) 函数f和g，每个函数计算相同的结果，期望相似的输入（假设他们期望列表，为了讨论），运行时间f不取决于列表的大小；的运行时间也没有g。

但是，如果f计算答案的步骤比 's 更复杂（或耗时）g，则f's 的运行时间将超过g's - 终止所需的秒数f（我们称之为 value fsec）将超过终止所需的秒数g（我们称之为 value gsec）。尽管如此，fsec也不gsec依赖于输入列表的大小——无论输入列表有多大或多小，它们都是相同的——但gsec总是小于fsec.

这是因为运行时不依赖于输入列表的大小，它们被归类为 O(1) 算法——而不是因为它们执行特定数量的操作。