Курс 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
- Тестирование времени с Freezegun
- Вызов функций по строке в Python.
- Реализация операции -= для пользовательского класса
- Дефолтные параметры в Python
- Рекурсия для обращения строки
- Переопределение метода __pow__
- Создание комплексных чисел
- Управление виртуальными окружениями в Python
- Импорт модулей в Python 3.12
- Логические значения в Python
- Капитализация строк
- Обновление множества в Python
- Метод radd для пользовательских чисел
- Курс Data Scientist в медицине
- Абстракции словарей и множеств в Python
- Метод rlshift для битового сдвига
- Отладка в командной строке
- Codecademy в Telegram
- Получение текущей директории
- Методы работы со списками
- Проверка кортежей.
- Оператор break в Python
- Лямбда-функции в цикле
- Функциональное программирование.
- Определение индекса элемента списка
- Enum в Python: создание и использование перечислений
- Оператор continue в Python
- Добавление элементов в список
- Установка и использование emoji
- Python 3.12: Псевдонимы типов
- Python Enumerate
- Официальный канал Python в Telegram
- Сортировка с помощью параметра key
- Импорт классов из другого файла
- Python Метод Union Множеств
- Библиотека itertools: объединение списков
- Преобразование объекта в строку
- Работа со слайсами
- Определение имен функций
- Метод join() для объединения строк
- Python и Монти Пайтон
- Проверка версии Python
- Область видимости переменных в Python
- Непрерывная проверка в Python
