查找If条件内的For循环的Big O表示法 [英] Finding Big O Notation of For loop which is inside an If condition

问题描述

sum = 0;
for( i = 1; i < n; ++i )
  for( j = 1; j < i * i; ++j )
    if( j % i == 0 )
      for( k = 0; k < j; ++k )
        ++sum;

如何找到此代码的Big O表示法?我是这个新的O记号事物的新手.因此，如果有人能简单地向我解释一下，我将不胜感激.谢谢！

How do I find Big O notation for this code? I'm new to this big o notation thing. So I'll appreciate if someone can explain me it simply with details.. Thank you!

推荐答案

大O是函数的渐近上限.因此，在您的情况下，如果if条件的求值始终为true，则for循环花费的时间最多，因此，您可以假定这获得了正确的上限，可能并不严格.但是在很多情况下，您不能做得更好.

Big O is an asymptotic upper bound of a function. So in your case the the for loops take the most time, if the if condition evaluates always to true, so you can just assume this an get a correct upper bound, which is maybe not tight. But there are a lot of cases where you cannot do better than this.

在某些情况下，您可以尝试删除if，同时大致保持操作数.例如.在您的情况下，可以将j = 1替换为j = i，将++j替换为j += i.这并不是要更改算法，而只是为了更改复杂性分析以改变您的看待方式.您仍然必须记住，中间的for循环采用了i*i的步骤.现在您有了:

In some cases you can try to remove the if while maintaining the number of operations roughly. E.g. in your case you could replace j = 1 by j = i and ++j by j += i. This is not to change the algorithm, but only for the complexity analysis to change the way you look at it. You still have to remember that the middle for loop takes i*i steps. Now you have this:

sum = 0;
for( i = 1; i < n; ++i )
  O(i * i) Operations
  for( j = i; j < i * i; j += i )
    for( k = 0; k < j; ++k )
      ++sum;

您还可以假定if条件始终为false.这样，您将获得一个下限.在某些情况下，上下限匹配，这意味着您要分析的部分实际上与总体复杂度无关.

You also can assume that the if condition is always false. This way you get a lower bound. In some cases the upper and lower bound match, meaning that the part you hat trouble to analyze is actually irrelevant for the overall complexity.

这篇关于查找If条件内的For循环的Big O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！