Курс 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. Основы работы с os
  5. Функция enumerate в Python
  6. Разделение списка на гнппы
  7. Декодирование байтов в строку
  8. Переопределение метода __or__()
  9. Преобразование PowerPoint в PDF.
  10. Docstring в Python
  11. Именование столбцов в Python с pandas
  12. Логирование с Loguru
  13. Декораторы в Python
  14. Блок else в циклах Python
  15. Поиск индексов в списке
  16. Непрерывная проверка в Python
  17. Создание и обучение модели с Keras
  18. Метод __float__ в Python
  19. Удаление ссылок в Python
  20. Именованные срезы в Python
  21. Оператор is в Python
  22. Отладка в Python
  23. Big O оптимизация
  24. Вызов функций по строке в Python.
  25. Запуск Python из интерпретатора
  26. Python: Фильтрация списков с помощью filter()
  27. Переопределение метода divmod
  28. Повторение элементов списков
  29. Модуль Operator в Python
  30. Исключение NotImplementedError
  31. Функции высшего порядка в Python
  32. Фильтры Pillow: NEAREST, BILINEAR, BICUBIC
  33. Работа с enumerate()
  34. Декораторы классов
  35. Использование функции enumerate()
  36. Метод ipow для возведения в степень
  37. Группы исключений в Python
  38. Отрицательные индексы списков в Python
  39. Оператор «not» в Python
  40. Передача аргументов через **arguments
  41. Лямбда-функции для min/max
  42. Поиск простых чисел
  43. Работа с модулем random
  44. Проверка условий: all и any
  45. Итераторы с потерямиZIP
  46. Группировка элементов в словарь

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

Добавить
свою компанию