Курс 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"
- Форматирование данных с помощью pprint
- Разбиение текста в Python
- Команда %dhist — список посещенных каталогов
- Вывод с переменной через запятую
- Тестирование с responses
- Область видимости переменных
- Печать списка с помощью метода join
- Обработка аргументов Python
- Проверка дубликатов в Python
- Управление мышью и клавиатурой с Pyautogui
- Сокращение ссылок с pyshorteners
- Python Тесты и Гайды
- Генерация QR-кодов с библиотекой qrcode
- Закрытие файла в Python
- Сериализация данных в JSON с помощью json.dumps
- Тип данных TypeVarTuple
- Модуль sys: основы
- Лямбда-функции в Python
- Преобразование списка в словарь через генератор
- Обработка исключений в Python
- Использование модуля math
- Итерация по коллекции в Python
- Создание таблиц в Python с PrettyTable
- Однострочники Python
- Pillow: работа с изображениями
- Создание GUI на Tkinter
- Работа со строками в Python
- Модуль inspect: получение информации о объектах
- Объединение словарей в Python
- Списки: объединение, изменение
- Метод setdefault() в Python
- Работа с файлами в Python
- Цепные операции в Python
- Удаление специальных символов с помощью re.sub
- Удаление элементов из списка в Python
- Обновление множества в Python
- Работа с изменяемыми списками
- Функция zip() — объединение последовательностей
- Поиск шаблона в строке
- Запуск внешнего кода в Jupyter
- Удаление дубликатов в pandas
- Оптимизация интернирования строк
- Гибкие функции Python
- Приоритет операций в Python
- Обработка исключений
- Очистка вывода в Python
