Курс 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"

  1. Оптимизация поиска в словарях
  2. Метод ne для сравнения объектов
  3. CSV строка разделение в Python
  4. Декоратор защиты анонимных пользователей
  5. Получение срезов итераторов
  6. Проблема сравнения словарей
  7. Установка пакетов с помощью pip
  8. Работа с массивами в Python
  9. Непрерывная проверка в Python
  10. Сокращение ссылок с pyshorteners
  11. Функции в одну строку
  12. Разделение списка на гнппы
  13. Декораторы классов
  14. Логирование с Loguru
  15. Получение обратного списка чисел
  16. Получение текущей директории
  17. Операции с комплексными числами
  18. Автоматизация скриптов на AWS Lightsail.
  19. Генератор списка в Python
  20. Генератор данных в Keras
  21. Форматирование строк с % в Python
  22. Скрытие вывода данных
  23. Flask — веб-фреймворк Python
  24. Генератор бросков кубиков
  25. Получение идентификатора объекта в памяти
  26. Установка библиотек в Python
  27. Оператор объединения словарей
  28. Округление чисел с помощью round
  29. Работа со стеком в Python
  30. Объединение словарей в Python
  31. Оператор in и not in в Python
  32. Обмен переменными в Jupyter
  33. Поиск наиболее частого элемента
  34. Работа с аргументами командной строки в Python
  35. Удаление файлов в Python
  36. Профилирование кода на Python
  37. Очистка данных с Pandas
  38. inspect в Python: анализ кода
  39. Абстракции словарей и множеств в Python
  40. Перевернуть список в Python
  41. Расчет времени выполнения
  42. Создание класса очереди
  43. Отправка POST-запроса в REST API
  44. Функция enumerate() в Python

Marketello читают маркетологи из крутых компаний