Курс 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
- Класс Counter() для подсчета элементов
- Управление виртуальными окружениями в Python
- Создание графиков в терминале
- Добавление элементов в список: append() vs extend()
- Применение функции к элементам списка
- Обработка исключений в Python
- Выключение компьютера с помощью Python
- Передача аргументов через **arguments
- Отправка HTTP-запросов в Python
- Список импортированных модулей в Python
- Замена текста в Python
- Форматирование строк в Python
- Структура строк в Python
- Работа с itertools
- Python: библиотеки и функции
- Функция pow() — возвести число в степень
- Создание и инициализация объектов
- Работа со словарями в Python
- Распаковка аргументов в Python
- Обновление и получение данных в SQLite
- Использование модуля __future__
- Нахождение самого длинного слова в списке с помощью max
- Фильтрация списка чисел
- Принципы Zen of Python
- Форматирование вывода списков
- Декоратор Property в Python
- Функция zip() в Python
- Расчет времени выполнения программы
- Отслеживание выполнения программы с библиотекой tqdm
- Создание словаря через dict comprehension
- Назначение максимального и минимального значения переменной в Python.
- Перегрузка операторов в Python
- Создание namedtuple из словаря
- Работа со слайсами
- Использование super() в Python
- Карта бомбоубежищ в Москве и Питере
- Глобальные переменные в Python
- Разница между датами
- Протокол управления контекстом
- %pinfo: получение информации об объекте
- Лямбда-функции в Python
- Модуль future Python
- List Comprehension Tutorial
