Курс 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. Удаление дубликатов из списка с помощью dict.fromkeys
  2. Работа с итераторами через срезы
  3. Инвертирование словаря
  4. Метод lt для сортировки объектов
  5. PUT запрос для обновления данных
  6. JSON-esque в Python
  7. Структурирование именованных констант
  8. Функция enumerate в Python
  9. Python: библиотеки и функции
  10. Генерация случайных чисел в Python
  11. Поиск самого частого элемента
  12. kwargs в Python
  13. Удаление falsy-значений из списка с помощью filter
  14. Список переменных с %who
  15. Работа с Path в Python
  16. Выход из профиля в Django
  17. Сравнение def и lambda функций в Python
  18. Метод join() для объединения элементов
  19. Тест скорости набора текста на Python
  20. Удаление эмодзи с помощью pandas
  21. Извлечение аудио из видео
  22. Тип данных TypeVarTuple
  23. Сложные типы данных в Python
  24. Создание новых списков в Python
  25. Работа с getopt
  26. Работа с библиотекой xkcd
  27. Асинхронное выполнение задач в процессах
  28. Копирование списков в Python
  29. Работа с геоданными с помощью geopy
  30. Отправка POST-запроса в REST API
  31. Извлечение статей с newspaper3k
  32. Python 3.12: переиспользование кавычек
  33. Профилирование с cProfile
  34. Использование defaultdict в Python
  35. Импорт модулей и пакетов в Python
  36. Flask — веб-фреймворк Python
  37. Ускорение выполнения кода в Python
  38. Python Enumerate
  39. Генерация QR-кодов с Python
  40. Лямбда-функции в Python
  41. Контроль точности вывода чисел
  42. Переопределение метода delitem в Python
  43. Протокол управления контекстом
  44. Конкатенация списков в Python

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

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