theory - 确定 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 的评论。循环逻辑不一定微不足道，可以排除。假设为了论证，您确信循环逻辑不会中断，逻辑是微不足道的（即没有影响所执行工作的条件路径），并且您将工作单元定义为总逻辑通过循环一次执行。

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

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