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

Question

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

 public static LinkedListNode nthToLast(LinkedListNode head, int k) {
    LinkedListNode p1 = head;
    LinkedListNode p2 = head;

    /* Move p1 k nodes into the list.*/
    for (int i = 0; i < k; i++) {
        if (p1 == null) return null; // Out of bounds
        p1 = p1.next;
    }

    /* Move them at the same pace. When p1 hits the end, 
     * p2 will be at the right element. */
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

Answer 1

Когда вы думаете о пространственной сложности алгоритма, вы должны учитывать дополнительное пространство, которое алгоритм явно выделяет. В приведенном выше примере алгоритм поиска nth до последнего LinkedListNode в списке просто создает два дополнительных LinkedListNode указателя p1 и p2, а также один счетчик i для итерации l oop. Объем дополнительной памяти, выделяемой алгоритмом, не имеет ничего общего с длиной передаваемого связанного списка. Вы по-прежнему будете использовать два указателя LinkedListNode и один целочисленный счетчик независимо от того, был ли связанный список, переданный в nthToLast(), иметь длину 10 узлов или 10 миллионов узлов. Следовательно, сложность этого алгоритма в пространстве равна O (1).

Answer 2

Сложность пространства - это объем памяти, используемый алгоритмом в зависимости от размера ввода. Другими словами: если размер ввода изменился, сколько памяти будет использовать алгоритм?

Имеет ли вход связанного списка узел 1, 10 узлов или 1000000 узлов алгоритм использует тот же объем памяти. Он использует постоянную сумму, потому что он только выделяет 3 переменных (постоянное число) - int i, LinkedListNode p1 и LinkedListNode p2.

ОБНОВЛЕНИЕ: Важно отметить, что p1 и p2 просто ссылка на один узел. Они инициализируются ссылкой на значение head, которое будет просто первым узлом в списке. Эти две переменные не содержат сам весь список.

   head
    |
    v
 [node1] --> [node 2] --> [node 3] --> ..... --> [node n]
  ^   ^
  |   |
 p1   p2

Обратите внимание на рисунке выше, что если бы у нас был 1 узел или 20 узлов, у вас все равно были бы только один p1 и p2. Они могут ссылаться на разные узлы в разное время в алгоритме, но каждый из них может содержать только один узел.

Answer 3

Алгоритм выполняет O (n) итераций, но он не выделяет никакой памяти для элементов в списке, он использует только уже существующие элементы. Используется только память для локальных переменных p1 и p2, используемых для обозначения элементов.