Блог

Я хотел подтвердить, правильно ли я получил big-O для нескольких фрагментов кода, включающих циклы for.

 for ( int a = 0; a < n; a   )
    for ( int b = a; b < 16 ; b   )
        sum  = 1;
  

Я думаю, что это O(16N) => O (N), но тот факт, что b начинается с a, а не 0 во втором цикле for, сбивает меня с толку.

 int b = 0;
for ( int a = 0; a < n ; a   )
    sum  = a * n;
    for ( ; b < n ; b   )
        sum  ;
  

Я хочу сказать O (N ^ 2), поскольку существуют вложенные циклы for, где оба цикла идут в n . Однако b во втором цикле использует инициализацию из внешней области, и я не уверен, влияет ли это на время выполнения.

 for (int a = 0; a < (n * n); a   )
    sum  ;
    if (a % 2 == 1)
        for (; a < (n * n * n); a   )
            sum  ;
  

Я понял, что первый цикл for равен O (N ^ 2), а тот, который находится под оператором if, равен O (N ^ 3), но я не знаю, как учитывать оператор if.

Первый O(n*min(n, 16)) из них заключается в том, что цикл 16 for считается O(1) предполагаемым n > 16 . если n < 16 тогда это O(n^2) .

Вторая O(n) причина заключается в том, что после первой итерации b уже n .

Третья O(n^3) причина заключается в том, что максимум после 2 итераций вы достигаете оператора if, а затем a увеличиваетесь до тех пор, пока n^3 это не означает, что в следующей итерации внешнего цикла for a<n*n действительно true, поэтому он полностью выйдет из цикла for.

Надеюсь, это ответит на ваши вопросы, удачи!