Курс 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. Форматирование данных с помощью pprint
  2. Разбиение текста в Python
  3. Команда %dhist — список посещенных каталогов
  4. Вывод с переменной через запятую
  5. Тестирование с responses
  6. Область видимости переменных
  7. Печать списка с помощью метода join
  8. Обработка аргументов Python
  9. Проверка дубликатов в Python
  10. Управление мышью и клавиатурой с Pyautogui
  11. Сокращение ссылок с pyshorteners
  12. Python Тесты и Гайды
  13. Генерация QR-кодов с библиотекой qrcode
  14. Закрытие файла в Python
  15. Сериализация данных в JSON с помощью json.dumps
  16. Тип данных TypeVarTuple
  17. Модуль sys: основы
  18. Лямбда-функции в Python
  19. Преобразование списка в словарь через генератор
  20. Обработка исключений в Python
  21. Использование модуля math
  22. Итерация по коллекции в Python
  23. Создание таблиц в Python с PrettyTable
  24. Однострочники Python
  25. Pillow: работа с изображениями
  26. Создание GUI на Tkinter
  27. Работа со строками в Python
  28. Модуль inspect: получение информации о объектах
  29. Объединение словарей в Python
  30. Списки: объединение, изменение
  31. Метод setdefault() в Python
  32. Работа с файлами в Python
  33. Цепные операции в Python
  34. Удаление специальных символов с помощью re.sub
  35. Удаление элементов из списка в Python
  36. Обновление множества в Python
  37. Работа с изменяемыми списками
  38. Функция zip() — объединение последовательностей
  39. Поиск шаблона в строке
  40. Запуск внешнего кода в Jupyter
  41. Удаление дубликатов в pandas
  42. Оптимизация интернирования строк
  43. Гибкие функции Python
  44. Приоритет операций в Python
  45. Обработка исключений
  46. Очистка вывода в Python

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