Как работает 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) — Вложенный цикл на одном и том же вводе.