Временная сложность прохождения связанного списка в два прохода

Question

Я знаю, что прохождение связанного списка от головы до хвоста занимает O (n) времени. Что если мы пройдем его дважды? Это все еще O (n), правильно? Потому что я в основном O (n + n) = O (2n) ~ O (n).

Answer 1

Да. В самом деле, вы можете сказать, что f(n) в O(n), f(2n) тоже в `O (n). Это происходит от определения символа.

По определению существует константа c > 0 и N0 такая, что f(n) < c * n для всех n > N0. Следовательно, f(2n) < c' * n для n >‌ N0 / 2 и константа c'. Следовательно, f(2n) тоже находится в O(n).

Обратите внимание, что утверждение "если f(n) в O(g(n)), также f(2n) в O(g(n))" вообще неверно! Пример противоречия - когда f(n) = g(n) = 2^n.