Курс 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
- Enum в Python
- Настройка Cron
- Работа с zip()
- Модуль os в Python: работа с файлами
- Декоратор Ajax required
- Хранение данных
- Работа со словарями
- Шаблоны и наследование в Flask
- Операторы присваивания в Python
- Именованные срезы в Python
- Декоратор защиты анонимных пользователей
- Взаимодействие с внешними процессами в Python
- Форматирование данных с pprint
- Метод rlshift для битового сдвига
- Подсчет количества элементов в списке
- Метод setdefault() в Python
- Подписка на каналы разработчиков
- Работа с файлами и директориями в Python.
- Метод hash в Python
- Переопределение метода delitem в Python
- Создание функций с произвольным количеством аргументов
- Работа со списками
- Создание генераторов в Python
- Установка и загрузка Instaloader
- Работа со стеком в Python
- Область видимости переменных
- Поиск простых чисел
- Принципы программирования
- Перезагрузка оператора в Python
- Присвоение значений переменным в Python
- Метод classmethod
- Основы Python за 14 дней
- Печать календаря
- Непрерывная проверка в Python
- Создание инструмента обнаружения плагиата
- Работа с переменными в Python
- Цикл for в Python
- Генераторы списков
- Список методов и атрибутов
- Работа с collections в Python.
- Поиск индексов в списке
- Декоратор Property в Python
- Печать в одной строке
- Повторение элементов в Python
- UserList в Python: Описание и примеры использования
- Хешируемые ключи в Python
- Переворот последовательности
