Какие знаешь сложности алгоритмов

Question

Young&Junior · Accepted Answer

Вот основные сложности алгоритмов в порядке возрастания:

O(1) - константная (доступ по индексу в массиве)

python

value = my_list[0]  # O(1)

O(log n) - логарифмическая (бинарный поиск)

python

def binary_search(arr, x):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: low = mid + 1
        elif arr[mid] > x: high = mid - 1
        else: return mid
    return -1

O(n) - линейная (поиск в неотсортированном массиве)

python

for item in my_list:  # O(n)
    print(item)

O(n log n) - линейно-логарифмическая (быстрая сортировка)

python

sorted_list = sorted(my_list)  # Timsort - O(n log n)

O(n²) - квадратичная (пузырьковая сортировка)

python

for i in range(len(arr)):      # O(n²)
    for j in range(len(arr)-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

O(2ⁿ) - экспоненциальная (рекурсивный Фибоначчи)

python

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # O(2ⁿ)

O(n!) - факториальная (перебор всех перестановок)

Также существуют:

O(n³) - кубическая (наивное умножение матриц)
O(nᵏ) - полиномиальная
O(n√n) - встречается в некоторых алгоритмах

Какие знаешь сложности алгоритмов

Следующий вопрос

Похожие вопросы