Big-O моей функции

Question

Я пытаюсь понять нотацию Big-O, поэтому я делал свой собственный пример для O (n), используя цикл while, так как я обнаружил, что циклы while немного сбивают с толку, чтобы понять в нотации Big O. Я определил функцию с именем linear_example, которая принимает список, например, python:

Итак, мой код:

def linear_example (l):
    n =10
    while n>1:
        n -= 1
        for i in l:
            print(i)

Мой мыслительный процесс - это код в цикле for, который выполняется за постоянное время O (1) и код в цикле while выполняется за O (n) раз. Таким образом, для него будет O (1) + O (n), который будет оцениваться в O (n).

Обратная связь

Answer 1

Придумайте простой цикл for:

for i in l:
    print(i)

Это будет O (n), так как вы перебираете список для скольких элементов в l. (Где n == len (l))

Теперь мы добавим цикл while, который делает то же самое десять раз, поэтому:

n + n + ... + n (x10)

И сложность O (10n).

Поскольку это все еще многочлен с первой степенью, мы можем упростить это до O (n), да.

Answer 2

Не совсем. Прежде всего, n не является фиксированным значением, поэтому O (n) не имеет смысла. Давайте для этого примем заданное значение M, заменив первые две строки:

def linear_example (l, M):
    n = M

Код в цикле for выполняется за O (1) время, при условии, что каждый элемент i из l имеет конечное ограниченное время печати. Однако цикл повторяется len(l) раз, поэтому сложность цикла составляет O (len (l)) .

Теперь этот цикл выполняется один раз полностью * через 1019 * для каждого значения n в цикле while, всего M раз. Следовательно, сложность составляет произведение сложностей петли: O (M * len (l)) .