Курс 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. Разделение строки на пары ключ-значение.
  2. Python: возвращение нескольких значений
  3. Переменные в Python: сокращение гласных
  4. Методы classmethod и staticmethod
  5. Numpy: использование Ellipsis
  6. Глобальные переменные в Python
  7. Установка и использование модуля «howdoi»
  8. Оператор is в Python
  9. Замена текста в Python
  10. Оператор (*) в Python
  11. Функциональное программирование.
  12. Удаление элемента по индексу
  13. Замена текста с re.sub()
  14. Проверка переменных окружения в Python
  15. Создание GUI на Tkinter
  16. Освобождение памяти в Python
  17. None в Python: использование и особенности
  18. Форматирование строк с % в Python
  19. Работа с комплексными числами
  20. Python defaultdict добавление ключа
  21. Абстракции словарей и множеств в Python
  22. Работа со слайсами
  23. Установка и использование Telegram API в Python
  24. Работа с коллекциями Python
  25. Работа со случайными элементами
  26. Упрощение условных выражений с тернарным оператором
  27. Замена символов в строке
  28. Декораторы в Python
  29. Преобразование многоуровневого словаря
  30. Применение функции map() в Python
  31. Работа с путями в Python
  32. Добавление элементов в список
  33. Python union() функция — объединение множеств
  34. Форматирование строк в Python.
  35. Преобразование данных в Python
  36. Проверка запуска скрипта или импорта модуля
  37. Проверка на палиндром
  38. Работа со строками
  39. Python: Фильтрация списков с помощью filter()
  40. Аннотации типов в Python
  41. Модуль subprocess: запуск внешних команд
  42. Модуль pprint
  43. Оператор морж в Python 3.8
  44. Эффективная конкатенация строк с использованием join()
  45. Использование super() в Python
  46. Метод get для словаря

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