Разница во времени в реализации Linkedlist (Итеративный VS Рекурсивный)?

Question

Меняется ли сложность времени в этих двух реализациях получения количества узлов в Linkedlist?

 private int getCountIterative() {

    Node start = head;
    int count = 0;
    while (start != null)
    {
        count++;
        start = start.next;
    }
    return count;
}


private int getCountRecursive(Node node) {
    if (node == null)
        return 0;
    return 1 + getCountRecursive(node.next);
}

Answer 1

TL; DR: все те же комплексы

Чтобы вычислить сложность операции (например, алгоритм поиска или сортировки - или ваш пример, подсчет), вам необходимо определить доминирующую операцию .

Для поиска и сортировки обычно используются сравнения. Какова ваша доминирующая операция? Давайте предположим, что это node.next, поиск следующего узла.

Тогда оба подхода имеют O (n) операций - так что это одинаковая сложность.

Обратите внимание, что эта временная сложность является упрощением. Есть факторы, которые игнорируются, такие как накладные расходы на вызовы функций. Так что это та же сложность, но это не обязательно говорит вам, какая версия быстрее.

Answer 2

Нет, сложность времени не изменится.

Однако производительность и общее время выполнения обычно хуже для рекурсивного решения, поскольку Java не выполняет Tail Call Optimization .