Как я могу вычислить сложность этого фрагмента кода?

Question

Я не могу рассчитать временную сложность этого кода.

for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
        //statement
    }
}

Нужна помощь.

Answer 1

Давайте попробуем посчитать операции. Проблема в том, какие операции актуальны? Временная сложность обычно выражается в нотациях большого О (или других асимптотических нотациях), потому что она скрывает сложность точного подсчета операций. Следовательно, все, что является константой, может быть посчитано как 1. Это не имеет значения, если есть 4 добавления или 40, важно то, сколько раз это повторяется. В конце концов, сколько раз statement выполняется.

Давайте посчитаем. Внешний цикл изменяется от 0 до n, а внутренний цикл - от i + 1 до n. Таким образом, когда i равно 0, внутренний цикл выполняет n-1 итераций, когда i равен 1, внутренний цикл выполняет n-2 итерации и т. Д., Пока i не станет n-1, и внутренний цикл больше не будет выполняться. Итак, мы имеем:

(n-1) + (n-2) + ... + 1 + 0

Всего там n терминов. Эта сумма последовательных чисел имеет довольно хорошо известную формулу: это (n-1) (n-2) / 2.

Расширяя продукт выше, мы получаем 1/2 (n ^ 2-3n + 2). И O (1/2 (n ^ 2-3n + 2)) эквивалентно O (n ^ 2).

Относительно того, почему все сводится к O (n ^ 2), есть много позадитеория асимптотической нотации, но на практике она сводится к «big-oh сохраняет самый значимый член в полиноме и отбрасывает коэффициенты» (легко доказывается с помощью определения big-Oh).

Answer 2

Для каждого i-го элемента второй цикл выполняется n- (i + 1) раз. В первом цикле for, когда i = 0, второй цикл выполняется n-1 раз
Аналогично, когда i = 1, второй цикл выполняется n-2 раза
.
.
.
, когда i= n-2 второй цикл запускается 1 раз.
, когда i = n-1 второй цикл выполняется 0 раз.
O (n-1) + O (n-2) + ...... + O(1) +0 => O (n)
Следовательно, общая временная сложность алгоритма составляет O (n * n) = O (n ^ 2)

Answer 3

O (n ^ 2)

Итерация начинается с n, когда i = 0, затем n-1, n-2, до достижения последней итерации, которая равна 0;

Итак, итогоитерация будет n + (n-1) + (n - 2) + 。。。 + 0 = O (N ^ 2)