Встречается на собеседованиях • сегодня

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

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

  1. O(1) - константная (доступ по индексу в массиве)
python
value = my_list[0]  # O(1)
  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
  1. O(n) - линейная (поиск в неотсортированном массиве)
python
for item in my_list:  # O(n)
    print(item)
  1. O(n log n) - линейно-логарифмическая (быстрая сортировка)
python
sorted_list = sorted(my_list)  # Timsort - O(n log n)
  1. 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]
  1. O(2ⁿ) - экспоненциальная (рекурсивный Фибоначчи)
python
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # O(2ⁿ)
  1. O(n!) - факториальная (перебор всех перестановок)

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

  • O(n³) - кубическая (наивное умножение матриц)
  • O(nᵏ) - полиномиальная
  • O(n√n) - встречается в некоторых алгоритмах
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

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

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы