Курс 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"
- Декораторы в Python
- Распаковка аргументов в Python
- Изменение переменной в Python: nonlocal
- Автоматизация скриптов на AWS Lightsail.
- Класс Counter() для подсчета элементов
- Определение локальных переменных в Python
- Colorama: окрашивание текста в Python
- Применение функции к каждому элементу списка
- Деление в Python
- Повторение элементов списков
- Работа с классами данных
- Введение в PyTorch
- Создание словарей и множеств в Python.
- Удаление URL-адресов в Python
- Вывод символов строки в Python
- Получение ID процесса
- Переворот списка в Python
- Логирование с Logzero
- Решатель судоку на Python с pygame
- Оператор «not» в Python
- Перемещение и удаление файлов в Python
- Бесконечная проверка в Python
- Библиотека wikipedia для Python
- Операторы Splat и splatty-splat
- Автоматизация с Python
- Оператор деления для класса Rational
- Уникальные значения из списка
- Метод count() для списков
- Списковое включение в Python
- Новшества Flask 2.0
- Работа со строками в Python.
- Счетчик ссылок в Python
- Декораторы в Python
- Проверка дублей в списке.
- Генерация случайных чисел в Python
- Использование обратной косой черты в f-строках
- Создание словарей в Python
- Метод Enumerate() для списков
- Анонимные функции Lambda
- Отладка кода
- Генерация тестовых данных с factory_boy
- Избегайте ошибку FileNotFoundError
