Что было бы худшим временем выполнения моих двух алгоритмов

Question

Мне очень трудно понять, как рассчитать время выполнения в худшем случае и время выполнения в целом.Поскольку есть цикл while, должно ли время выполнения быть n + 1, потому что цикл while должен запускаться еще 1 раз, чтобы проверить, является ли случай все еще действительным? Я также искал в Интернете хорошее объяснение / практику о том, какрассчитать эти времена выполнения, но я не могу найти ничего хорошего.Ссылка на что-то подобное будет очень цениться.

def reverse1(lst):
    rev_lst = []
    i = 0
    while(i < len(lst)):
       rev_lst.insert(0, lst[i])
       i += 1
    return rev_lst

def reverse2(lst):
    rev_lst = []
    i = len(lst) - 1
    while (i >= 0):
       rev_lst.append(lst[i])
       i -= 1
    return rev_lst

Answer 1

Поскольку число итераций фиксировано для любого заданного размера списка ввода для обеих функций, «наихудшая» временная сложность будет такой же, как и «лучшая», и среднее значение здесь.

In reverse1, операция вставки элемента в список с индексом 0 стоит O (n) , потому что она должна копировать все элементы на их следующие позиции и в сочетании с циклом while, который повторяется дляКоличество раз размера входного списка, сложность времени reverse1 будет O (n ^ 2) .

Нет такой проблемы в reverse2,однако, поскольку метод append стоит всего лишь O (1) , его общая временная сложность составляет O (n) .

Answer 2

Я собираюсь дать вам математическое объяснение того, почему дополнительные итерации и операции с постоянным временем не имеют значения.

Это O (n), поскольку определение Big-Oh таково для f(n) ∈ O (g (n)) существует некоторая постоянная k такая, что f (n)

Рассмотрим алгоритм со временем выполнения, представленным как f (n) = 10000n + 15000000. Можно упростить это, выделив n: f (n) = n (10000 + 15000000 / n).Для наихудшего случая времени выполнения вам важна производительность алгоритма только для очень больших значений n.Поскольку в этом упрощении вы делите на n, во второй части, когда n становится действительно большим, коэффициент n будет приближаться к 10000, так как 15000000 / n приближается к 0, если n огромно.Следовательно, для n> N (это означает, что для достаточно большого значения n) должна существовать постоянная k, такая что f (n)

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

Answer 3

Постоянные коэффициенты или дополнительные значения не имеют значения для времени выполнения big-O, так что вы слишком усложняете это.Время выполнения составляет O(n) (линейное) для reverse2 и O(n**2) (квадратичное) для reverse1 (поскольку list.insert(0, x) само по себе является O(n) операцией, выполняемой O(n) раз).

Расчеты времени выполнения Big-O связаны с тем, как алгоритм ведет себя при увеличении размера ввода до бесконечности, и меньшие факторы здесь не имеют значения;O(n + 1) совпадает с O(n) (как и O(5n) в этом отношении; при увеличении n постоянный множитель 5 не имеет отношения к изменению во время выполнения), O(n**2 + n) все еще O(n**2) и т. д.