为什么:
算法A的运行时间至少为O(n²)
没有意义?
插入排序算法的运行时间不超过O(n²)
是正确的吗?
我试着上网，但没有得到一个好的解释。
我还有一个问题:
我知道任何线性函数a·n+b都是O(n)和O(n²)它也是O(n³)吗?
T(n): Algo a的运行时间，我们只关心T(n)的上界和下界语句:T(n) >= O(n^2)
上界:因为T(n) >= O(n^2)，所以没有T(n)上界的信息下界:假设f(n) = O(n^2)，则语句:T(n) >= f(n)，但f(n)可以是任何比n^2"小"的东西，例如:constant, n,...，因此也没有关于T(n)下界的结论
=>语句没有意义
一个原因可能是没有上界的下界不是很有用。"至少"意味着在正常情况下它可以是指数级的。如果你不知道上界，你可能无法在实际应用中使用该算法，因为你无法知道程序是否在宇宙结束之前结束。
大0符号在正确使用时表示上界。所以把下界写成大0是在滥用符号。
说"无意义"是一个很重的词。这当然是有用的信息，即使它不充分。如果你的问题有更多的背景，你会得到更好的帮助。
类比:
这句话有点像说:"我家屋顶的高度至少是地面的高度。"
O(n^2)是最坏的情况，这意味着a的运行时间将是n^2或更快。如果它的运行时间至少是O(n^2)那么这意味着A的最快运行时间，至少是O(n^2)这意味着它也可以比0 (n^2)慢。这些语句意味着A可以拥有任何可能的运行时
我知道任何线性函数an+b都是O(n)和O(n²)它是O(n^3) ?
是的，它是。大0符号表示一个完整的函数集合。但是我们应该尽可能地用它来描述一个函数。虽然f(n) = an+b确实是O(n^2)甚至O(n^3)，但更准确的说法是f(n) = O(n) .
0符号，也就是说:f(x)属于集合O(g(x)f (x) & lt;C * g(x)，对于所有C(实数)
。你的算法不能增长超过一个二次函数
这不是没有意义的，如果你不知道确切的算法，它可以被使用，但你肯定知道它需要O(n^2)次操作。
例如，如果一个人不知道排序算法，但知道要对数组进行排序，我们至少需要查看每个元素，那么他可以说"对数组进行排序至少需要O(n)"。
因为没有人关心它在最好的情况下有多快，最坏的情况才是重要的。通常人们都想知道在最坏的情况下需要多少钱。
设f(n)为算法的运行时间。
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
对于f(n)，这总是正确的，因为运行时间总是非负的。因此，该语句是多余的。
算法A的运行时间至少为O(n²)
让我们假设算法A
的运行时间T(n) = O(log n)
从这里我们已经有
T(n) <= c.log n
这个命题试图通过至少O(n²)来表达的是
T(n) <= c.n²
=> c.log n <= c.n² #for some c>0 and n>=n0
这是很明显的。当我们已经知道T(n) <= c.logn时，说T(n) <= c.n2不会增加价值。
所以，当我们已经有一个算法的下界或上界时，说这个下界(分别)是最小或最大，不会增加任何我们已经不知道的新信息。
回答你的第二个问题
我知道任何线性函数a·n+b都是O(n)和O(n²)它是O (n³)?
是的。根据上界(大0)的定义，它的意思是
a.n+b <= c.n
如果这个为真那么这个也为真
a.n+b <= c.n³
"A算法的运行时间至少为O(n2)"等价于"A算法的运行时间为Big Omega(n2)"，并非无意义