确定for循环的时间复杂度

Question

我知道这个循环是O(n^2)，但是什么是Big-Omega和Big-Theta？在这样的情况下，如何计算它们呢？

for(i = 0; i < array.length; i++) 
   for (j = 0; j < array.length; j++)
      //bla bla

Answer 1

对于初学者，请参阅larsmans‘s comment。循环逻辑不一定要足够简单才能排除。为了便于论证，假设您确信循环逻辑不会中断，该逻辑是微不足道的(即，没有影响所执行工作的条件路径)，并且您正在将您的工作单元定义为通过循环在一次传递中执行的总逻辑。

在这种情况下，您的上界和下界是相同的。您可以保证执行至少且至多N^2个单元的工作。您有一个Ω(N^2)和一个O(N^2)。你的下界和上界是相同的；你可以表征Θ(N^2)。

值得一提的是，如果循环逻辑不是微不足道的，并且特别依赖于您实际定义的工作单元，那么这是没有意义的。这些符号的要点是描述算法将招致的预期工作量。您可以在一个循环中迭代数百万次，但是如果您真正关心的工作是在该循环中调用SomeExpensiveFunction()的次数，并且逻辑规定它只被调用一次，那么这不会影响这种表示法。