Курс Python → Big O оптимизация
Big O оптимизация — это важная задача для разработчиков. Оценка скорости работы программы на разных устройствах может быть сложной из-за различий в аппаратном обеспечении. Для универсальной оценки был разработан подход, использующий понятие Big O. Например, простой алгоритм перебора всех значений имеет сложность O(n), где n — количество значений, так как используется только один цикл. Если же есть два вложенных цикла, как в программе для вывода таблицы умножения, то сложность уже будет O(n^2). Из формул видно, что второй алгоритм работает намного медленнее.
Главное правило — чем больше данных, тем дольше будет работать программа. Например, бинарный поиск имеет сложность O(log n) и работает намного быстрее, но требует отсортированного списка. При оценке сложности учитывается количество проходов по данным, а не количество строк кода. График скорости работы алгоритмов показывает, что чем меньше операций выполняется, тем лучше.
Пример кода:
def linear_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1
def binary_search(array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
В приведенных примерах кода показаны алгоритмы линейного и бинарного поиска. Линейный поиск имеет сложность O(n), так как выполняет n операций в худшем случае. Бинарный поиск имеет сложность O(log n) и работает быстрее, но требует отсортированного списка. Понимание Big O помогает разработчикам выбирать наиболее эффективные алгоритмы для своих задач.
Другие уроки курса "Python"
- Избегание изменяемых аргументов
- Работа с изменяемыми коллекциями
- Профилирование с Pandas
- Оператор «not» в Python
- Проверка элементов списка условием
- Метод enumerate() в Python
- Работа с коллекциями Python
- Изменение списка срезами
- Разработка игры Pong с turtle
- Цикл for в Python
- Именованные кортежи в Python
- Генераторы списков в Python
- Установка User-Agent в Python
- Псевдонимы в Python
- Создание новых списков
- Работа с массивами в Python
- Счетчик в Python: most_common()
- Работа с файловой системой в Python
- Игра «Виселица» на Python
- Измерение потребления памяти при сортировке
- Работа с срезами в Numpy
- Очистка входных данных
- Обработка ошибок в Python
- Создание генераторов в Python
- Модуль os: работа с файлами и папками
- Декоратор Ajax required
- Логирование с Logzero
- Дефолтные параметры в Python
- Изменение элемента списка
- Объединение списков в Python
- Генерация UUID в Python
- Вакансии в Nebius
- Профилирование данных с Pandas.
- discard() — удаление элемента из множества
- Работа с YAML в Python: PyYAML.
- Лямбда-функции в Python
- Работа с эмодзи в Python
- Работа с дробями в Python
- Генерация тестовых данных с factory_boy
- Работа с модулем glob в Python
- Получение срезов итераторов
- Использование подчеркивания в REPL
- Создание графиков в терминале
- Получение текущего времени в Python
- Преобразование регистра символов
