Курс 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. Генераторы в Python
  2. Реализация операции -= для пользовательского класса
  3. Преобразование многоуровневого словаря
  4. Модуль array: создание и использование массивов
  5. Нахождение отличий в списках
  6. Проблема сравнения словарей
  7. Функции map, filter, reduce
  8. Переменная Шредингера
  9. Непрерывная проверка в Python
  10. Генератор данных в Keras
  11. Преобразование текста в речь с Python
  12. Модуль os: работа с файлами и папками
  13. Получение частей дроби
  14. Создание графики с черепахой
  15. Работа с комплексными числами
  16. Python enumerate() функции
  17. None в Python: использование и особенности
  18. Измерение времени выполнения
  19. Многопоточность и асинхронное программирование в Python
  20. Замеры производительности в Python
  21. Импорт модуля из другого каталога
  22. Flask: создание веб-приложений
  23. Сортировка элементов в Python
  24. Компиляция регулярных выражений
  25. Форматирование строк в Python
  26. Работа с буфером обмена на Python
  27. Библиотека sh: удобные команды терминала
  28. Метод remove() для удаления элемента из списка
  29. PEP-401: оператор
  30. Декораторы в Python
  31. Форматирование объектов с модулем pprint
  32. Библиотека wikipedia для Python
  33. Python: Фильтрация списков с помощью filter()
  34. Работа с коллекциями Python
  35. Путь к интерпретатору Python
  36. Измерение времени выполнения с помощью time
  37. Метод count() для списка
  38. Избегайте изменяемых аргументов
  39. Установка максимального количества цифр
  40. Магические методы в Python
  41. Векторизация в Python с NumPy.
  42. Область видимости переменных
  43. Многострочные комментарии в Python
  44. Python Enum Weekday Usage

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