Курс 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. Вывод переменной и строки в Python
  3. Работа с парами ключ-значение
  4. Оператор is в Python
  5. Подсчет вхождений элементов
  6. Настройка вывода в Numpy
  7. Генераторы в Python
  8. Сортировка данных в Python
  9. Подсказки типов в Python
  10. Измерение времени выполнения кода с использованием time
  11. Модуль math: константы π и e
  12. Работа с CSV файлами в Python
  13. Numpy: объединение массивов
  14. Метод округления чисел
  15. JMESPath в Python
  16. Умножение строк и списков
  17. Переопределение метода divmod
  18. Шаблоны и наследование в Flask
  19. Логирование с Loguru
  20. Создание словарей в Python
  21. Методы работы со строками в Python
  22. Форматирование строк с помощью f-строк
  23. Создание циклической ссылки
  24. Проверка наличия элемента в списке
  25. Работа с часовыми поясами в Python
  26. Передача аргументов в Python
  27. Копирование объектов в Python
  28. Обработка исключений с блоком else
  29. Подчеркивание в REPL
  30. Область видимости переменных
  31. Работа с утверждениями в Python
  32. Конвертация текстовых чисел с помощью Numerizer
  33. Списковое включение в Python
  34. Метод rxor для операции побитового исключающего «или»
  35. Python Calendar Usage
  36. Парсинг веб-страниц с Beautiful Soup
  37. Генераторы словарей и множеств
  38. Работа с collections в Python.
  39. Сложение матриц в NumPy
  40. Форматирование кода на Python
  41. Работа с массивами в Python

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