Как считать сложность операции сравнения?

Question

[zlodiak]

#!/usr/bin/env python3

a = [3, 2, 6, 34, 5]    # O(n)
for i in range(5):      # O(n)
    if a[i] > 5:        # ?
        print(a[i])     # O(1)

Помогите пожалуйста посчитать сложность. У меня проблема со строкой:
if a[i] > 5:

как понимаю, здесь придётся оценивать две операции(извлечение из словаря по ключу и сравнение >). Видимо, расчёт сложности для этой строки выглядит так?

O(1) + O(1) = O(2) -> константы сокращаем до единицы -> O(1)

В итоге сложность всего алгоритма получилась такая:

O(n) + O(n) + O(1) + O(1) = O(2n) + O(2) -> константы сокращаем до единицы -> O(2n + 1)

Comments

[Roman K]

Зачем тебе всё это вообще? Есть смысл оценивать сложность АЛГОРИТМОВ, а не всех кусков кода.

[zlodiak]

Roman Kitaev, а я не вижу разницы :) Ведь алгоритм состоит из строк

[Roman K]

P.S. O(2n + 1) — некорректно. Константы выбрасываются. O-нотация показывает РОСТ СЛОЖНОСТИ при увеличении N, а не фактическое количество операций. Так что будет O(n). Вернее даже, будет O(1), потому что твой массив содержит константное количество элементов — 5 штук. Тут нечему вырастать.

[Roman K]

zlodiak, Ты занимаешься ерундой, в которой нет практического смысла. Разобраться со сложностью основных структур и алгоритмов — отлично. Ты же пытаешься применить О-нотацию к тому, к чему её нельзя применять. Где у тебя тут N, скажи?

[zlodiak]

Roman Kitaev, я правильно понимаю, что учитывать нужно только то, что может возрастать, то есть N. а строки, которые характеризуются только константами(например if a[i] > 5 ) нужно просто игнорировать?

[Roman K]

zlodiak, да

Answer 1

[Михаил Макаров]

Это не словарь, а список. Пишут, что в питоне доступ к элементу по индексу имеет сложность O(1), уж не в курсе, как в нём списки реализованы.

Comments

[Roman K]

Списки — это массивы. Доступ по индексу за O(1) же

[Михаил Макаров]

Roman Kitaev, честно говоря, я до настоящего момента думал, что там честный (одно- или двух-) связный список, а оказывается, что немного сложнее. Первое, что на Хабре нашёл:
https://habr.com/ru/post/273045/

[Roman K]

Михаил Макаров, я давно понял, что Гвидо его так назвал, чтобы вычислять дилетантов :) С другой стороны, логично же, что доступ по индексу за O(1) у (сколько-угодно-) связных списков не бывает.

[longclaps]

Roman Kitaev, самое обескураживающее, что я по этому поводу видел - это реализация на питоне лисповских списков в лисп-стиле. Чистые функции, много рекурсии, никакого ООП и полный а*уй. Что-то вроде

def push(l, a):
    return (l, a)

def pop(l):
    tail, a = l
    return tail, a

def getbyidx(l, i):
    tail, a = pop(l)
    return getbyidx(tail, i - 1) if i else a

def setbyidx(l, i, b):
    tail, a = pop(l)
    return (setbyidx(tail, i - 1), a) if i else (tail, b)

Неизгладимое впечатление.