Курс 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. Подсказки при вводе данных в Python
  4. Поиск уникальных и повторяющихся элементов
  5. Оператор * в Python
  6. Работа с комбинациями в Python.
  7. Enum в Python
  8. Работа с timedelta
  9. Функция map() и ленивая оценка
  10. Обработка исключений в Python
  11. Команда %dhist — список посещенных каталогов
  12. Использование обратной косой черты в f-строках
  13. Преобразование текста в нижний регистр
  14. Colorama: окрашивание текста в Python
  15. Распаковка аргументов в Python
  16. Определение имен функций
  17. Автоматизация скриптов на AWS Lightsail.
  18. Создание namedtuple из словаря
  19. Многопроцессорное программирование в Python
  20. Таймер обратного отсчета
  21. Работа с итераторами через срезы
  22. Ускорение выполнения кода в Python
  23. Профилирование данных с Pandas
  24. Декоратор total_ordering для класса Point
  25. Функции all и any в Python
  26. Поиск элементов BeautifulSoup
  27. Обработка ошибки IndexError
  28. Использование type hints
  29. TON Smart Challenge #2: участие и подготовка
  30. Конвертация коллекций в Python.
  31. JMESPath в Python
  32. Генерация случайных чисел Python
  33. Рациональные числа в Python
  34. Howdoi — получение ответов из терминала
  35. Динамические маршруты во Flask
  36. Изменение регистра данных
  37. Игра «Камень, ножницы, бумага» — Python
  38. Сериализация и десериализация объектов
  39. Сглаживание списка
  40. Pretty-printing JSON в Python
  41. Генераторы в Python
  42. Блок else в Python
  43. Цикл for с enumerate() в Python
  44. Поиск кода
  45. Форматирование данных с pprint

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