Как вычислить итоговую сложность?

Question

[zlodiak]

Есть такой код:

#!/usr/bin/env python3

a = [10, 20, 30, 40, 50, 60]

for i in range(len(a)):
    print(i, a[i])

LIVE DEMO здесь.

Скажите пожалуйста, правильный ли подход я использовал чтобы вычислить итоговую сложность этого кода?

len(a) # O(1)
for i in (0, 1, 2, ,3 ,4 ,5) # O(n)
print() # O(1)

итоговая сложность: (O(1) * O(n)) * O(1) = O(n)

Answer 1

[Дмитрий Подболотов]

Все верно

Comments

[zlodiak]

Дмитрий Подболотов честно говоря, у меня были сомнения по поводу print(i, a[i]).
Если бы было print(a[i]), то я бы даже не стал сомневаться, что O(1). Но, как видите, в принте по сути 2 операции, а не одна...

[Дмитрий Подболотов]

Это не важно т.к выполняется за константу

[jcmvbkbc]

print(i, a[i])
выполняется за константу

Дмитрий Подболотов, ну если уж совсем строго, то за O(log (n)) выполняется print.

[dmshar]

jcmvbkbc,
А можно поподробнее, как вывод элемента по индексу дает сложность O(log (n)) ?

[jcmvbkbc]

как вывод элемента по индексу дает сложность O(log (n)) ?

dmshar, неправильный акцент. Правильный акцент -- как вывод индекса дает сложность O(log (n)). Поскольку индекс пробегает значения от 0 до n-1, в нём в худшем случае log(N) цифр. Это, конечно, не имеет значения для типов фиксированной ширины, но чисто теоретически...