Курс 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 Метод sleep() из time
  3. Замена текста в Python
  4. Метод rename() для переименования файлов и каталогов
  5. Группировка элементов Python
  6. Оператор морж в Python 3.8
  7. Декораторы в Python
  8. Переворот списка в Python
  9. Модуль future Python
  10. Генерация UUID в Python
  11. Создание генераторов
  12. Установка и использование pyshorteners
  13. Оператор (*) в Python
  14. Отделение звука от видео
  15. Замер времени выполнения кода
  16. Конкатенация списков в Python
  17. Навыки Python: строки, типы данных
  18. Транспонирование 2D-массива с помощью zip
  19. Использование функции enumerate()
  20. Функции map, filter, reduce
  21. Множественное наследование в Python
  22. Защита данных в Python
  23. Сортировка данных с лямбда-функциями
  24. Поиск анаграмм с Counter
  25. Работа с словарями в Python
  26. Лямбда-функции в Python
  27. Модуль xkcd: добавление юмора в Python
  28. Создание даты из строки ISO
  29. Переопределение метода __floordiv__
  30. IPython и Jupyter Notebook: руководство
  31. Возврат нескольких значений
  32. Удаление элементов во время итерации
  33. Работа с массивами в Python
  34. Однострочники Python
  35. Установка и использование Logzero
  36. Модуль sys: основы
  37. Декоратор total_ordering для класса Point
  38. Создание вкладок с TKinter
  39. Импорт модулей в Python 3.12
  40. Обмен значений переменных в Python
  41. Раздувающийся словарь в Python
  42. 9 уловок для чистого кода
  43. Python и Монти Пайтон
  44. Метод setitem в Python
  45. Изменение объектов в Python
  46. Округление банкира в Python

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

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