Курс 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"
- Установка Git и AWS CLI
- Создание новых списков в Python
- Замеры производительности в Python
- Создание вложенных циклов for
- Многострочные комментарии в Python
- Управление памятью в numpy.
- Удаление ключа из словаря
- Удаление дубликатов из списка с помощью dict.fromkeys
- Combobox в Tkinter
- Удаление дубликатов из списка
- Перемещение и удаление файлов в Python
- Измерение времени выполнения кода
- Пустой оператор pass в Python
- Функция format() в Python
- Изменение регистра данных
- Генераторы в Python
- Группы исключений в Python
- Создание даты из строки ISO
- Создание объекта timedelta
- Метод get() для словарей
- Функция pow() — возвести число в степень
- Инверсия списка/строки в Python
- Работа с модулем cmath
- Добавление кнопки в tkinter
- Оператор del в Python
- Динамические маршруты во Flask
- Удаление специальных символов
- Применение команды break
- Управление фоновыми задачами в Python
- Оператор Walrus в Python
- Измерение потребления памяти при сортировке
- Измерение времени выполнения с помощью time
- Метод repr() в Python
- Переопределение метода divmod
- Установка и обучение ChatterBot
- Нахождение разницы между списками в Python
- Модуль math: основные функции
- Python Метод sleep() из time
- Работа с необработанными строками
- Очистка входных данных
- Monkey Patching в Python
- Оператор распаковки в Python
- Автоматизация с Python
- Пространство имен в Python
- Удаление дубликатов с помощью множеств
- Оператор match в Python
- Метод setdefault() в Python
