查找复杂性的下限和上限

Question

我想找到这个算法复杂度的下限和上限

1: for all i=1 to n*n do
2:   for all j=i to 2*i do
3:     output “hello world”
4:   end for
5: end for

通过将其写下来为求和并将其简化为

f(n) = 0.5*n^4 + 1.5*n^2

似乎复杂度的上限是 O(n^4(，因为 0.5*n^4 是最重要的元素。

对于复杂性的下限，我使用了公式

f(n) = Ω(g(n)) if f(n) >= c * g(n), where c > 0

似乎 0

对于这两种情况，我的推理是否正确？ 有没有更简单的方法可以找到欧米茄？ 感谢您抽出宝贵时间:)

Answer 1

我很确定你的代码的语法是静态的，所以上限和下限是相等的。

编辑：我从排序算法中知道复杂性符号。迭代次数取决于排序的方式，当然还有列表的初始顺序。排序算法通常是已排序列表中最快的。因此，最好的情况是对所有内容进行排序，最坏的情况(某种混乱(取决于算法。一些算法将在简单的反转列表中挣扎，而其他算法则不会。这就是为什么没有完美的排序算法。您可以选择最适合您的情况。