Какова сложность пространства и времени для этой функции, которая получает узел в связанном списке на основе его положения из хвоста?

Question

Какова сложность пространства и времени (наихудший случай) для следующего решения?

Node getNodeFromTail(Node head, int x){
    Node p = head;
    Node q = head;

    int diff = 0;

    while (p.next != NULL){
        p = p.next;

        if (diff >= x)
            q = q.next;
        else
            diff++;
    }
    return q;
}

Это объяснение кода выше:
Возьмите эту ссылку список для примера: 1 -> 2 -> 3 -> 4 -> 5

x == значение из хвоста,
, когда x равен 0, результат должен быть 5
когда x равен 1, результат должен быть 4
, когда x равен 2, результат должен быть 3 и так далее.

Вот что я думаю:
Сложность пространства
Константа O (1)

Сложность времени
в то время как l oop просматривает связанный список в O (n) время ;
, где n = длина связного списка.

Однако, я думаю, что есть дополнительная сложность из-за выражения if , которое, как мне кажется, должно быть O (nx) время Таким образом, мы получаем: O (n) * O (nx) , что почти общая сложность времени составляет O (n ^ 2) (т.е. квадрати c) .
У меня просто такое ощущение, что в худшем случае это не совсем линейное время.
Это правильно?

Ссылка: { ссылка }

Answer 1

Сложность по времени O (n) или линейная. Условие while l oop зависит только от инструкции p = p-> next внутри l oop. Другие инструкции внутри l oop выполняются в постоянное время и не влияют на состояние времени l oop. Таким образом, мы можем заключить, что l oop выполняется ровно n раз (если список имеет длину n элементов).
Также обратите внимание, что внутри l сначала нет l oop, в то время как l oop, как вы предлагаете в вашем вопросе.