Курс 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. Метод __ilshift__ для битового сдвига влево
  3. Импорт с альтернативным именем
  4. Форматирование строк с f-строками
  5. Цикл for в Python
  6. Python: отсутствие точек с запятыми
  7. Создание Radio кнопок в tkinter
  8. Создание OrderedDict
  9. Оператор распаковки в Python
  10. Методы работы со списками
  11. Howdoi — получение ответов из терминала
  12. Непрерывная проверка в Python
  13. Оператор is в Python
  14. Автоматизация с Python
  15. Библиотека Chartify: руководство
  16. Определение индекса элемента списка
  17. Округление дробей в Python
  18. Группы исключений в Python
  19. Библиотека sh: использование команд bash в Python
  20. Именованные кортежи в Python
  21. Объединение словарей в Python
  22. Метод difference_update() — разность множеств
  23. Установка и использование emoji
  24. Установка и использование модуля «howdoi»
  25. Работа со словарями Python
  26. Установка random seed в Python
  27. Namedtuple в Python
  28. Принцип одной функции
  29. Хеши в Python
  30. Переопределение метода delitem в Python
  31. Получение имени функции с помощью inspect
  32. Нарезка списков в Python
  33. Запрос DELETE с библиотекой requests
  34. Отделение звука от видео
  35. Разделение строки с регулярными выражениями
  36. GitHub в Telegram: подписка на уведомления
  37. Метод classmethod
  38. Списки в Python: основы
  39. Методы и функции в Python
  40. Удаление и повторная вставка ключа в OrderedDict
  41. Извлечение аудио из видео
  42. Проверка элементов списка условием
  43. Структуры данных в Python
  44. Лямбда-функции в defaultdict
  45. Измерение времени выполнения кода
  46. Декоратор проверки активности
  47. Инверсия списка и строки

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

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