O(n) и функция временной сложности данного кода

Question

если следующая структура цикла находится в разделе Анализ верхней границы. Вычисляет ли он по-прежнему O(n^2)? Я смущен, поскольку внутренний цикл зависит от внешнего цикла, и с каждой внешней итерацией внутренний цикл for зацикливается на один раз меньше. В дополнение к тому, что есть O(n), функция временной сложности будет «n!.N +C», где C - константа? Я предполагаю! из-за внутренней петли.

      for(int i=n;i>0;i--)
{
 for(int j=i;j>=1;j--)
  {
     count++;
  }
}

Answer 1

Этот код имеет ту же временную сложность, что и код в вопросе.

      for(int i = 0; i < n; i++){  // outer loop
    for(int j = 0; j < i; j++){  // inner loop
        count++;
    }
}

На первой итерации внешнего цикла (i = 0) внутренний цикл не выполняется.

Во второй итерации внешнего цикла (i = 1) внутренний цикл выполняет once.

На третьей итерации внешнего цикла (i = 2) внутренний цикл выполняет twice.

Итак, на последней итерации внешнего цикла (i = n) внутренний цикл выполняет n times.

Следовательно, общее количество выполнений этого кода равно

1 + 2 + 3 + … + n

= n(n + 1) / 2

= ((n^2) + n) / 2

= O(n^2)

Answer 2

Допустим, внешний цикл переходит к n, а внутренний цикл переходит к значению внутреннего цикла. (случай разворота вашего цикла). полные внутренние циклы подсчета вы можете рассчитать по формуле

Сумма k = 1..n (k) = n * (n+1) / 2 = 1/2 * n^2 + 1/2 n

так что у вас есть временная сложность

O(1/2 * n^2 + 1/2 n) = O(n² + n) = O(n²)