Постоянное время O(1) в Python

Один шаг при любом размере

O(1) означает постоянное время: операция выполняется за одно и то же число шагов, будь во входных данных 5 элементов или миллион. Объём работы вообще не растёт.

Это самая лучшая сложность из возможных. Типичные операции O(1) в Python: чтение элемента списка по индексу, чтение значения словаря по ключу, len(), добавление одного элемента и простая арифметика.

Обратите внимание, чего O(1) не означает: это не «быстро», а «не становится медленнее при росте входных данных». Один постоянный шаг может быть и медленным, но он остаётся одним шагом.

Поиск в списке и словаре

Элемент списка находится в известном месте памяти, поэтому words[2] — это один переход: компьютер не перебирает элементы перед ним. В списке из миллиона элементов такое чтение стоит столько же.

Поиск в словаре, например ages["Ben"], в среднем тоже выполняется за постоянное время: ключ сразу указывает словарю, где хранится значение. Если ключа нет, квадратные скобки вызывают KeyError, поэтому для поиска часто используют ages.get("Ben") — этот метод возвращает значение или None, если ключа нет.

Чтение элемента по индексу

Программа читает один элемент из списка из 5 элементов и один — из списка с миллионом элементов. Оба чтения занимают один шаг: длина списка не играет роли.

Напишите программу на Python с маленьким списком из 5 слов и большим списком из миллиона целых чисел, созданным с помощью генератора списка. Прочитайте по одному элементу из каждого по индексу и выведите оба, чтобы показать, что чтение по индексу — это один шаг, какой бы длины ни был список.

> Вывод: полная программа на Python

Prompt

Напишите программу на Python с маленьким списком из 5 слов и большим списком из миллиона целых чисел, созданным с помощью генератора списка. Прочитайте по одному элементу из каждого по индексу и выведите оба, чтобы показать, что чтение по индексу — это один шаг, какой бы длины ни был список.

Вывод: полная программа на Python

words = ["one", "two", "three", "four", "five"]

big = [i * 2 for i in range(1000000)]

# По одному шагу на каждое чтение, какой бы длины ни был список.
print(words[2])
print(big[999999])

Чтение значения по ключу

ages.get("Ben") сразу находит 25. Для отсутствующего ключа "Dan" возвращается None, а get("Dan", 0) вместо этого возвращает запасное значение 0 — тоже за постоянное время.

Напишите программу на Python со словарём, сопоставляющим имена и возраст: Ana 30, Ben 25 и Cleo 41. Найдите Ben с помощью get() и выведите результат. Затем найдите отсутствующий ключ Dan с помощью get() и выведите результат, а потом ещё раз — с помощью get() и запасного значения 0.

> Вывод: полная программа на Python

Prompt

Напишите программу на Python со словарём, сопоставляющим имена и возраст: Ana 30, Ben 25 и Cleo 41. Найдите Ben с помощью get() и выведите результат. Затем найдите отсутствующий ключ Dan с помощью get() и выведите результат, а потом ещё раз — с помощью get() и запасного значения 0.

Вывод: полная программа на Python

ages = {"Ana": 30, "Ben": 25, "Cleo": 41}

print(ages.get("Ben"))

print(ages.get("Dan"))
print(ages.get("Dan", 0))

Добавление и простая арифметика

append() добавляет один элемент в конец списка. Чаще всего это один шаг. (Время от времени список должен увеличиться и копируется, но в среднем стоимость одного добавления остаётся постоянной.)

Все мелкие операции — присваивания, сложения, сравнения, обмен двух значений — тоже O(1). Именно в этих «шагах» измеряются все остальные классы сложности.

Добавление одного элемента

append() помещает "yellow" в конец. Стоимость не зависит от того, сколько цветов уже есть в списке.

Напишите программу на Python со списком, содержащим red, green, blue. Выведите список и его длину, добавьте yellow, затем снова выведите список и его длину.

> Вывод: полная программа на Python

Prompt

Напишите программу на Python со списком, содержащим red, green, blue. Выведите список и его длину, добавьте yellow, затем снова выведите список и его длину.

Вывод: полная программа на Python

colors = ["red", "green", "blue"]
print("до:   ", colors, "длина:", len(colors))

colors.append("yellow")
print("после:", colors, "длина:", len(colors))

Обмен двух значений

a, b = b, a меняет два значения местами за один шаг с постоянным временем — вспомогательная переменная не нужна.

Напишите программу на Python с двумя переменными a = 1 и b = 2. Выведите их, поменяйте местами с помощью присваивания двух значений a, b = b, a и снова выведите их.

> Вывод: полная программа на Python

Prompt

Напишите программу на Python с двумя переменными a = 1 и b = 2. Выведите их, поменяйте местами с помощью присваивания двух значений a, b = b, a и снова выведите их.

Вывод: полная программа на Python

a, b = 1, 2
print("до:   ", a, b)

a, b = b, a
print("после:", a, b)