Big-O和Omega符号

具有O(n)的大O下界

也就是说, f(n) ϵ O(g(n)) 如果为,则为true |f(n)| <= k|g(n)| n 趋向无穷大( by definition

假设我们有一个函数 f(n) = n 2 (也就是说,如果忽略常数因子,插入排序的最坏情况)。我们可以说 n 2 ϵ O(n 2 ) ,但我们也可以说 n 2 ϵ O(n 3 ) 或 n 2 ϵ O(n 4 ) 或 n 2 ϵ O(n 5 ) 或

g(n) 我们可以找到的是 n 2 .

看到我贴在那里的答案了吗。

也许我误解了?

不,你是对的。

对于最坏情况下的插入排序,上界为O(n ^2.