временная сложность переменных циклов

Question

Я хочу попытаться вычислить O (n) моей программы (в Python). Есть две проблемы:

1: у меня есть базовые знания о O (n) [иначе: я знаю, что O (n) имеет отношение ко времени и вычислениям)

и

2: все циклы в моей программе не имеют какого-либо конкретного значения. они основаны на входных данных.

Answer 1

n в O(n) означает в точности размер ввода. Итак, если у меня есть этот код:

def findmax(l):
    maybemax = 0
    for i in l:
        if i > maybemax:
            maybemax = i
    return maybemax

Тогда я бы сказал, что сложность равна O(n) - сколько времени занимает пропорционально входному размеру (поскольку цикл повторяется столько раз, сколько длина l).

Если бы у меня было

def allbigger(l, m):
    for el in l:
        for el2 in m:
            if el < el2:
                return False
    return True

затем, в худшем случае (то есть когда я возвращаю True), у меня есть один цикл длины len(l), а внутри него - один цикл длины len(m), поэтому я говорю, что это O(l * m) или O(n^2) если ожидается, что списки будут примерно одинаковой длины.

Answer 2

Попробуйте начать, затем перейдите на вики:

• Обычное английское объяснение обозначения Big O