“所有 O(1) 函数的运行时间完全相同。” 对或错?任何人都可以向我解释答案吗?
user1795758
问问题
3105 次
1 回答
12
错误的。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) 算法——而不是因为它们执行特定数量的操作。
于 2012-11-03T01:51:19.850 回答