Какова функция стоимости big-O этого алгоритма?

Question

Как бы вы охарактеризовали нижеследующее в обозначении big-O?

rotors = [1,2,3,4,5 ...]
widgets = ['a', 'b', 'c', 'd', 'e' ...]

assert len(rotors) == len(widgets)

for r in rotors:
    for w in widgets:
        ...

    del widgets[0]

Answer 1

Это O (n ^ 2). Вы можете видеть, что количество выполнений внутреннего цикла:

n + (n - 1) + (n - 2) + ... + 1

потому что один виджет удаляется при каждой итерации внешнего цикла. То есть (n ^ 2 + n) / 2, то есть O (n ^ 2).

Answer 2

, поскольку вы проходите через оба цикла, это O (n ^ 2).

Answer 3

Из-за утверждения:

assert len(rotors) == len(widgets)

ответы O (n ² ) верны, но в общем случае, когда списки не обязательно имеют одинаковую длину, вы бы назвали это O (m * n).

Answer 4

Этот алгоритм будет иметь худшую производительность O (n ^ 2).

Answer 5

С риском быть и противоположным, и педантичным, вы действительно не предоставили достаточно информации, чтобы ответить на вопрос в общих чертах. Конечно, производительность не лучше, чем O (n ^ 2), но, поскольку вы не дадите подробностей о том, что вы делаете во внутреннем цикле, в общем, будет намного хуже. Однако, если предположить, что во внутреннем цикле происходит O (1), то общая производительность равна O (n ^ 2).

Answer 6

Это O (n ^ 2), но я думаю, что людям не хватает удаляемой части этого вопроса.

The first loop you have n widgets.
The second loop you have n-1 widgets.
...
The n-1 loop you have 2 widgets.
The n loop you have 1 widgets.

Вы можете подумать, что вы понижаете Big-O, но все, что делает удаление, умножает коэффициент на 1 / 2.

Это потому, что n + (n-1) + ... + 2 + 1 = n (n + 1) / 2. Когда N уходит в бесконечность, оно превращается в n ^ 2/2, что является просто O (n ^ 2)

Answer 7

Да, именно поэтому эти большие проблемы О всегда трудно понять. Но если бы мне пришлось угадывать, я бы сказал O (n ^ 2), поскольку вы проходите через 2 для циклов, каждый раз выполняя некоторую операцию.