Имеют ли значение признаки неравенства при оценке времени выполнения?

Question

Разница между foo1 и foo2 заключается в знаках равенства в цикле for.Когда мы оцениваем время выполнения, как неравенство влияет на наш результат?

int foo1(int n)
{
   int i, j, x = 0;

   for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)

        x++;

    return x;
}

int foo2(int n)
{
   int i, j, x = 0;

   for (i = 1; i < n; i++)
      for (j = 1; j < n; j++)

        x++;

    return x;
}

Answer 1

Циклы с <= могут быть переписаны в циклы с помощью < и наоборот.

int foo1(int n)
{
   int i, j, x = 0;
   for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        x++;
    return x;
}

int foo2(int n)
{
   int i, j, x = 0;
   for (i = 1; i <= (n-1); i++)
      for (j = 1; j <= (n-1); j++)
        x++;
    return x;
}

Теперь мы можем видеть, что циклы в foo1 оба цикла n раз, давая foo1 O (n²), тогда как циклы в foo2 оба цикла (n-1) раз, давая foo2 O ((n-1) ²) = O (n²-2n + 1),что также отражается в возвращаемых значениях для x.

С точки зрения общей сложности, обе функции рассматриваются как O (n²), поэтому, используете ли вы < или <=, на самом делеважно, по крайней мере, в циклах, подобных тем, которые вы показали.