algorithm - 寻找复杂性的下限和上限

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 < c < 1，下限似乎是 Ω(n^3)

我的推理对这两种情况都正确吗？有没有更容易找到欧米茄的方法？感谢您的时间 ：）

Answer 1

我很确定您的代码的复杂性是静态的，因此上限和下限是相等的。

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