Курс 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
- Поиск уникальных и повторяющихся элементов
- Оператор * в Python
- Работа с комбинациями в Python.
- Enum в Python
- Работа с timedelta
- Функция map() и ленивая оценка
- Обработка исключений в Python
- Команда %dhist — список посещенных каталогов
- Использование обратной косой черты в f-строках
- Преобразование текста в нижний регистр
- Colorama: окрашивание текста в Python
- Распаковка аргументов в Python
- Определение имен функций
- Автоматизация скриптов на AWS Lightsail.
- Создание namedtuple из словаря
- Многопроцессорное программирование в Python
- Таймер обратного отсчета
- Работа с итераторами через срезы
- Ускорение выполнения кода в Python
- Профилирование данных с Pandas
- Декоратор total_ordering для класса Point
- Функции all и any в Python
- Поиск элементов BeautifulSoup
- Обработка ошибки IndexError
- Использование type hints
- TON Smart Challenge #2: участие и подготовка
- Конвертация коллекций в Python.
- JMESPath в Python
- Генерация случайных чисел Python
- Рациональные числа в Python
- Howdoi — получение ответов из терминала
- Динамические маршруты во Flask
- Изменение регистра данных
- Игра «Камень, ножницы, бумага» — Python
- Сериализация и десериализация объектов
- Сглаживание списка
- Pretty-printing JSON в Python
- Генераторы в Python
- Блок else в Python
- Цикл for с enumerate() в Python
- Поиск кода
- Форматирование данных с pprint















