Курс 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. Docstring в Python
  3. Непрерывная проверка в Python
  4. Красивый вывод списка
  5. Работа с итераторами через срезы
  6. Метод radd для пользовательских чисел
  7. Установка переменной среды в Python
  8. Чтение бинарного файла в Python.
  9. Скрытие вывода данных
  10. Слияние словарей в Python 3.9
  11. Переворот списка в Python
  12. Объединение списков в Python
  13. Основы Python за 14 дней
  14. Подсчет элементов в Python
  15. Оператор match в Python
  16. Генераторы списков в Python
  17. Подсчет элементов с помощью Counter
  18. Замена переменных в Python
  19. Комментарии в Python
  20. Создание списка дат
  21. Очистка входных данных
  22. Проверка дубликатов в Python
  23. Инверсия списка/строки в Python
  24. Объединение строк с помощью метода join
  25. Именованные срезы в Python
  26. Magic Commands — улучшение работы с Python
  27. Оптимизация строк в Python
  28. Метод join() для объединения строк
  29. Игра Виселица на Python
  30. Структурирование именованных констант
  31. Выключение компьютера с помощью Python
  32. Определение индекса элемента списка
  33. Блок else в циклах Python
  34. Разделение строки на подстроки в Python
  35. Работа с множествами в Python
  36. Работа со списками
  37. Метод enumerate() в Python
  38. Изменение элемента списка
  39. Форматирование вывода с F-строками
  40. Метод ior для битовых операций
  41. Исправление ошибки NameError
  42. Оператор «not» в Python
  43. Бесконечные списки в Python
  44. Конвертация текстовых чисел с помощью Numerizer
  45. Генерация UUID в Python
  46. Фильтрация входных данных в Python
  47. Поиск простых чисел

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

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