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

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

1 голос
/ 03 февраля 2020

Приведенный ниже код имеет пространственную сложность 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;

}

Ответы [ 2 ]

3 голосов
/ 03 февраля 2020

Сколько места ему нужно по отношению к значению 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;

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

sum += 2 * i + l;

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

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

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

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

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

2 голосов
/ 03 февраля 2020

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

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

...