Большое О

Big O notation

O(1)
Это нотация постоянного времени. Время выполнения остается постоянным независимо от размера входных данных. Например, доступ к элементу в массиве по индексу и вставка/удаление элемента в хэш-таблице.

O(n) Линейная нотация времени. Время выполнения растет прямо пропорционально размеру входных данных. Например, поиск максимального или минимального элемента в несортированном массиве.

O(log n)
Логарифмическая нотация времени. Время выполнения медленно увеличивается по мере увеличения входных данных. Например, бинарный поиск в отсортированном массиве и операции над сбалансированными бинарными деревьями поиска.

O(n^2)
Квадратичная нотация времени. Время выполнения растет экспоненциально с размером входных данных. Например, простые алгоритмы сортировки, такие как пузырьковая сортировка, сортировка вставкой и сортировка выбором.

O(n^3)
Кубическая нотация времени. Время выполнения быстро увеличивается по мере увеличения размера входных данных. Например, умножение двух плотных матриц с использованием наивного алгоритма.

O(n logn)
Линейная нотация времени. Это смесь линейного и логарифмического роста. Например, эффективные алгоритмы сортировки, такие как сортировка слиянием, быстрая сортировка и сортировка кучей

O(2^n)
Экспоненциальная нотация времени. Время выполнения удваивается с каждым новым элементом ввода. Например, рекурсивные алгоритмы решают задачи, разделяя их на несколько подзадач.

O(n!)
Факториальная нотация времени. Время выполнения резко возрастает с размером ввода. Например, задачи генерации перестановок.

O(sqrt(n))
Квадратная нотация времени. Время выполнения увеличивается относительно квадратного корня ввода. Например, поиск в диапазоне, таком как решето Эратосфена, для нахождения всех простых чисел до n.