Курс 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
- Вывод с переменной через запятую
- Избегайте ошибку FileNotFoundError
- Искажение имен в Python
- Конструктор в Python
- Изменение IP-адреса в Python
- Использование модуля __future__
- Хеши в Python
- Функции высшего порядка в Python
- Отладка кода
- Работа со случайными элементами
- Функция __init__ в Python
- Преобразование данных в Python
- Отладка утечек памяти в Python
- Преобразование чисел в Python
- Переменные в Python: сокращение гласных
- Импорт модулей в Python 3.12
- Преобразование регистра строк
- Метод __complex__ в Python
- Преобразование типов данных в set comprehension
- Обработка исключений с блоком else
- Оператор match в Python
- Динамическая типизация в Python
- Очистка данных в Python
- Получение списка кортежей из словаря
- Операции с кортежами
- Magic Commands — улучшение работы с Python
- Срезы в Python
- Метод get для словарей
- Оператор += для объединения строк
- Работа с Telegram API на Python
- Расчет времени выполнения кода
- Импорт в Python: список all
- Фильтрация списка от «ложных» значений
- Повторение элементов списков
- Создание словаря в Python
- Роль object и type в Python
- Настройка вывода NumPy
- Запуск внешних программ с subprocess
- Проблемы с dict в Python
- Создание копии итератора
- Использование функции product
- Удаление специальных символов с помощью re.sub
- Python и Юникод: работа с цифрами
- Декоратор проверки активности
- Сортировка и разворот списка
- Поиск самого частого элемента
