Курс 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"
- Вычисление натурального логарифма в NumPy
- Хранение данных с помощью dataclasses
- Работа со строками
- Метод lt для сортировки объектов
- Перезапуск ячейки в Jupyter Notebook с dostoevsky
- Форматирование строк с f-строками
- Создание словаря через dict comprehension
- Форматирование строк в Python
- Метод index() в Python
- Многоточие в Python
- Получение ID процесса
- Проблема сравнения словарей
- Создание панели меню Tkinter
- Установка и использование библиотеки google
- Декораторы для регистрации функций
- Подсчет вхождений элементов
- Избегание изменяемых аргументов
- Метод rsub в Python: расширение функциональности вычитания
- ChainMap избыточные ключи
- Генераторы данных
- Работа с функцией next() в Python
- JMESPath в Python
- Создание именованных кортежей в Python
- Управление сессиями в Python
- Идентификатор объекта в Python
- Генераторы списков
- Разделение строки с помощью re.split()
- Метод join() для объединения строк
- Удаление пробелов методом translate()
- Методы работы со списками
- Метод enumerate() в Python
- Удаление первого элемента списка
- Замеры производительности в Python
- Модуль array: создание и использование массивов
- Эффективная конкатенация строк с использованием join()
- Обработка аргументов Python
- Работа с timedelta в Python
- Проблема с изменяемыми аргументами
- Курсы Яндекс Практикум
- Работа с *args и **kwargs в Python
- Новшества Flask 2.0
- Освобождение памяти в Python
- Python: отличительная особенность — отступы
- Сравнение def и lambda функций в Python
- Инициализация переменных
- Генерация случайных данных в NumPy
