Почему временная сложность нижеследующего фрагмента O (n), а пространственная сложность O (1)

Приведенный ниже код имеет пространственную сложность O (1). Я знаю, что это как-то связано со стеком вызовов, но я не могу его правильно визуализировать. Если бы кто-нибудь мог заставить меня понять это немного яснее, было бы здорово.

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0;i < n; i++) {
        sum += pairSum(i, i + l);
    }
    return sum;
}

int pairSum(int a, int b) {

 return a + b;

}

time-complexity space-complexity
person Shorya Sharma    schedule 03.02.2020    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Сколько места ему нужно относительно значения n?

Единственная используемая переменная - sum. sum не меняется по отношению к n, поэтому он постоянный.

Если он постоянный, то это O (1)

Сколько инструкций будет выполнено по отношению к значению n?

Давайте сначала упростим код, а затем проанализируем его построчно.

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += 2 * i + l;
    }
    return sum;
}

Объявление и инициализация переменной занимают постоянное время и не меняются со значением n. Следовательно, эта линия - O (1).

int sum = 0;

Точно так же для возврата значения требуется постоянное время, поэтому оно также O (1)

return sum;

Наконец, давайте проанализируем внутреннюю часть for:

sum += 2 * i + l;

Это также постоянное время, поскольку в основном это одно умножение и две суммы. Снова O (1). Но этот O (1) он вызывается внутри for:

for (int i = 0; i < n; i++) {
   sum += 2 * i + l;
}

Этот цикл for будет выполняться ровно n раз. Следовательно, общая сложность этой функции составляет:

C = O(1) + n * O(1) + O(1) = O(n)

Это означает, что для этой функции потребуется время, пропорциональное значению n.

person Tommaso Fontana    schedule 03.02.2020
comment
Большой! Спасибо я поняла :) - person Shorya Sharma; 03.02.2020

arrow_upward
2
arrow_downward

Сложность во времени / пространстве O (1) означает постоянную сложность, и константа не обязательно равна 1, это может быть произвольное число, но оно должно быть постоянным и не зависеть от n. Например, если у вас всегда было 1000 переменных (независимо от n), это все равно даст вам O (1). Иногда может даже случиться, что константа будет настолько большой по сравнению с вашим n, что O (n) будет намного лучше, чем O (1) с этой константой.

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

person bezirganyan    schedule 03.02.2020