Курс 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. Создание задания в Cron
  2. Декодирование строк в Python
  3. Python enumerate() использование
  4. Анонимные функции в Python
  5. Объявление переменных в Python
  6. Concrete Paths в Python
  7. Метод __imod__ для Python
  8. Работа с временем в Python
  9. Зарезервированные слова в Python
  10. Работа с zip-архивами в Python
  11. Цикл for в Python
  12. Управление ресурсами с контекстными менеджерами
  13. Виртуальное окружение Python
  14. Переопределение метода __pow__
  15. Печать комбинаций в Python с Itertools
  16. Работа с массивами в Python
  17. Просмотр внешних файлов в %pycat
  18. Метод classmethod
  19. Метод add для класса Vector
  20. Создание матрицы в Python
  21. Использование *args
  22. Списки в Python: основы
  23. Установка Python3.7 и PIP
  24. Передача аргументов через **arguments
  25. Импорт классов из другого файла
  26. Создание генераторов
  27. Декораторы классов
  28. Оператор «is not» в Python
  29. Получение значений из словарей
  30. Определение объема памяти объекта
  31. Сложные типы данных в Python
  32. Удаление элементов по срезу
  33. Проверка типа объекта в Python
  34. Создание класса в Python
  35. Назначение максимального и минимального значения переменной в Python.
  36. Работа с enumerate()
  37. Поиск частых элементов в списке
  38. Роль object и type в Python
  39. Навыки Python: строки, типы данных
  40. Оператор «or» в Python
  41. Создание словаря через dict comprehension
  42. Вычисление времени выполнения
  43. Итерация по копии коллекции
  44. Создание инструмента обнаружения плагиата
  45. Прокачанный трейсинг ошибок

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