为什么是这样的说法：
算法A的运行时间至少为O(n²)
没有意义吗？
插入排序算法的运行时间最多为 O(n²)
这是正确的吗？
我尝试了网络，但无法得到很好的解释。
我有另一个问题：
我知道任何线性函数 a⋅n+b 都是 O(n) 也是 O(n²)。它也是O（n³）吗？
问问题
17191 次
10 回答
15
T(n)T(n)
: Algo A 的运行时间。我们只关心语句的上限和下限：T(n) >= O(n^2)
Upper bound: 因为T(n) >= O(n^2), 那么没有关于T(n)
Lower bound: Assume 的上界的信息: Assume f(n) = O(n^2), 然后是语句: T(n) >= f(n), 但f(n)可能是任何比n^2, Ex:更“小”的东西constant, n,..., 所以没有关于下界的结论T(n)too
=> 声明毫无意义
于 2013-03-16T04:34:07.563 回答
8
一个原因可能是没有上限的下限不是很有用。“至少”意味着在正常情况下它可以是指数的。如果您不知道上限，您可能无法在实际应用程序中使用该算法，因为您无法知道程序是否在 Universe 完成之前完成。
正确使用大 O 表示法表示上限。因此，将下限声明为大 O 是在滥用该符号。
说“无意义”是一个强烈的词。即使它不充分，它当然也是有用的信息。为您的问题提供更多背景信息，您可以获得更好的帮助。
于 2013-03-04T06:56:22.663 回答
2
一个比喻：
这句话有点像说：“我家屋顶的高度至少是地面。” 没错，但完全没有信息。
于 2018-01-14T07:05:14.960 回答
1
O(n^2) 是最坏的情况，这意味着 A 的运行时间将是 n^2 或更快。如果它的运行时间至少为 O(n^2)，那么这意味着 A 可以拥有的最快运行时间至少为 O(n^2)。这意味着它也可能比 O(n^2) 慢。这些语句意味着 A 可以有任何可能的运行时。
于 2013-09-16T22:34:09.397 回答
1
我知道任何线性函数 an+b 都是 O(n) 也是 O(n^2)。它也是 O(n^3) 吗？
是的。big-O 符号表示整个函数集合。但是我们应该用它来尽可能接近地描述一个函数。虽然这是真的，f(n) = an+b甚至O(n^2)是O(n^3)这样说更准确f(n) = O(n)。
于 2014-01-06T23:46:53.283 回答
0
O-notation，换句话说，意味着：f(x) 属于集合 O(g(x)) 如果 f(x) < C * g(x)，对于所有 C（那些是实数）
即您的算法不会增长超过二次函数
于 2013-03-04T07:26:13.950 回答
0
这不是没有意义的，例如，如果您不知道确切的算法，可以使用它，但您当然知道它需要 O(n^2) 操作。
例如，如果一个人不知道排序算法，但知道要对数组进行排序，我们至少需要查看每个元素，那么可以说“对数组进行排序至少是 O(n)”。
于 2013-03-04T09:37:51.433 回答
0
因为没有人关心它在最佳情况下的运行速度有多快，所以最坏的情况很重要。通常人们有兴趣知道在最坏的情况下需要多少。
于 2013-03-04T15:54:24.837 回答
0
设f(n)为算法的运行时间。
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
这对于 总是如此f(n)，因为运行时间总是非负数。因此，该声明是多余的。
于 2013-08-04T15:04:43.457 回答
-3
“算法A的运行时间至少为O(n2)”等价于“算法A的运行时间是Big Omega(n2)”，所以不是没有意义。
于 2013-03-04T07:16:50.343 回答