Некоторые алгоритмы с разной временной сложностью:

• O(1) — константная сложность. 13 Время выполнения не зависит от объёма входных данных: алгоритм всегда выполняется за одинаковое количество операций. 1 Пример — функция сложения двух чисел. 1
• O(n) — линейная сложность. 15 Время выполнения увеличивается пропорционально объёму входных данных: если объём увеличивается в 5 раз, то время выполнения тоже пятикратно увеличивается. 1 Классический пример — поиск минимального значения. 1
• O(log n) — логарифмическая сложность. 15 Такие алгоритмы уменьшают объём данных для обработки на каждой итерации. 1 Время работы логарифмических алгоритмов растёт медленно относительно увеличения объёма входных данных, поэтому их относят к эффективным. 1 Пример — бинарный поиск в отсортированном массиве. 1
• O(n log n) — линейно-логарифмическая сложность. 15 Возникает, когда в алгоритме комбинируется перебор всех элементов и уменьшение их количества на каждой итерации. 1 По эффективности такие программы располагаются между линейной и квадратичной сложностью. 1
• O(n²) — квадратичная сложность. 15 Время работы зависит от квадрата объёма входных данных, квадратичная сложность свойственна некоторым алгоритмам сортировки, например, сортировке пузырьком. 1
• O(n!) — факториальная сложность. 15 Это наименее эффективные алгоритмы: их скорость быстро падает с увеличением объёма входных данных. 1
• O(n³) — кубическая сложность. 5 Время выполнения зависит от размера входных данных в кубе. 5 Например, алгоритмы, которые имеют три вложенных цикла, такие как некоторые методы многомерной обработки данных. 5
• O(2ⁿ) — экспоненциальная сложность. 2 Время на выполнение таких алгоритмов растёт в степени n к размеру входных данных. 2 Одним из примеров может служить рекурсивный алгоритм Фибоначчи. 2