какова временная сложность вложенного цикла for, который повторяет n - 1 - i?

Question

Итак, если у меня есть такой цикл?

int x, y, z;
for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < n - 1 - i; j++){
        x = 1;
        y = 2;
        z = 3;
    }
}

, поэтому мы начнем с определения x, y, z, чтобы у нас было 4 операции, int i = 0 происходит один раз, i < n - 1 и i++ повторяется n - 1 раз, int j = 0, повторяется n - 1 раз, j < n - 1 - i и j++ повторяется (n - 1) * (n - 1 - i), а xyz = 1 также повторяет (n - 1) * (n - 1 - i). Так что, если бы я упростил это, вышеприведенный код работал бы на O(n^2)?

Answer 1

поэтому мы начнем с определения x, y, z, чтобы у нас было 4 операции

Это не обязательно, нам нужно только считать критические операции (т.е. в этом случае как частотело цикла выполняется).

Так что, если бы я упростил это, вышеприведенный код выполнялся бы за O (n²)?

Функция T(n) находится вO(g(n)) if T(n) <= c*g(n) (в предположении n >= n0) для некоторых констант c > 0, n0 > 0.

Так что для вашего кода тело цикла выполняется n - i раз для каждого i из которых nИтак, мы имеем:

Что действительно верно для c = 1/2, n0 = 1. Поэтому T(n) ∈ O(n²).

Answer 2

Вы правы, что сложность O (n ^ 2). Существует более одного способа подойти к вопросу о том, почему.

Формальный способ - подсчитать количество итераций внутреннего цикла, которое будет n-1 в первый раз, затем n-2, затемn-3, ... вплоть до 1, что дает в общей сложности n * (n-1) / 2 итераций, что составляет O (n ^ 2).

Неформальный способ сказатьвнешний цикл выполняется O (n) раз, и «в среднем» i примерно равно n / 2, поэтому внутренний цикл выполняется в среднем примерно (n - n / 2) = n / 2 раза, что также равно O(п). Таким образом, общее количество итераций составляет O (n) * O (n) = O (n ^ 2).

При использовании обоих этих методов недостаточно просто сказать, что тело цикла выполняет итерацию O (n^ 2) раза - нам также нужно проверить сложность тела внутреннего цикла. В этом коде тело внутреннего цикла просто выполняет несколько присваиваний, поэтому он имеет сложность O (1). Это означает, что общая сложность кода составляет O (n ^ 2) * O (1) = O (n ^ 2). Если бы вместо этого внутреннее тело цикла выполняло, например, двоичный поиск по массиву длины n, то это было бы O (log n), а общая сложность кода, например, составила бы O (n ^ 2 log n).

Answer 3

Да, вы правы. Временная сложность этой программы будет O (n ^ 2) в худшем случае.