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

Приведи примеры сложности алгоритмов

O(1) - Константная сложность
Пример: доступ к элементу массива по индексу.

python
arr = [1, 2, 3]
print(arr[0])  # O(1)

O(n) - Линейная сложность
Пример: поиск элемента в неотсортированном списке.

python
def linear_search(arr, target):
    for item in arr:  # O(n)
        if item == target:
            return True
    return False

O(log n) - Логарифмическая сложность
Пример: бинарный поиск в отсортированном массиве.

python
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:  # O(log n)
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

O(n²) - Квадратичная сложность
Пример: пузырьковая сортировка.

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

O(2ⁿ) - Экспоненциальная сложность
Пример: рекурсивное вычисление чисел Фибоначчи.

python
def fibonacci(n):
    if n <= 1:  # O(2ⁿ)
        return n
    return fibonacci(n-1) + fibonacci(n-2)
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

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

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

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