Как работает Big O

* Big O показывает, насколько медленнее становится код при увеличении входных данных.

* Для конкретного алгоритма существуют три случая: наилучший, средний и наихудший.

* Кроме того, существуют оценки Big O для эффективности использования времени, памяти и хранилища.

* Big O помогает понять, какие структуры данных или алгоритмы демонстрируют лучшую производительность.

* Big O показывает скорость роста, а не фактическую скорость выполнения. Поэтому важно тестировать входные данные на практике.

Сложность Big-O

* O(1) — Доступ к значению в хеш-таблице по ключу.

* O(n!) — Добавление вложенного цикла для каждого ввода.

* O(2^n) — Наивное рекурсивное вычисление последовательности Фибоначчи.

* O(log n) — Алгоритмы «разделяй и властвуй».

* O(n) — Проход по списку.

* O(n log n) — Итерации, использующие «разделяй и властвуй».

* O(n^2) — Вложенный цикл на одном и том же вводе.

Источник: vk.com

Комментарии: