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

Question

<分区>

Answer 1

错了。 O(1) 表示常数时间。这意味着无论输入的大小是多少，函数运行的时间或多或少是相同的 - 运行时间不会随着输入的变化而变化。

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

但是，如果 f 使用比 g 更复杂(或更耗时)的步骤来计算答案，那么 f' s 运行时间将超过 g - f 终止所需的秒数(我们称此值为 fsec)将更多g 终止所需的秒数(我们称此值为 gsec)。尽管如此，fsec 和 gsec 都不依赖于输入列表的大小——无论输入列表有多大或多小，它们都是相同的——但是 gsec 将始终小于 fsec。

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