Какие алгоритмы имеют квадратичную сложность O(n²)?

Пузырьковая сортировка (Bubble Sort) Сортировка выбором (Selection Sort) Сортировка вставками (Insertion Sort) Обход вложенных циклов, где каждый цикл зависит от размера входных данных (например, поиск пар в массиве)

Короткий ответ

Что ответить на собеседовании

Пузырьковая сортировка (Bubble Sort) Сортировка выбором (Selection Sort) Сортировка вставками (Insertion Sort) Обход вложенных циклов, где каждый цикл зависит от размера входных данных (например, поиск пар в массиве)

Подробный разбор

Ответ с пояснениями

  • Пузырьковая сортировка (Bubble Sort)
  • Сортировка выбором (Selection Sort)
  • Сортировка вставками (Insertion Sort)
  • Обход вложенных циклов, где каждый цикл зависит от размера входных данных (например, поиск пар в массиве)

Пример вложенных циклов:

def find_pairs(arr):
    n = len(arr)
    for i in range(n): # O(n)
        for j in range(n): # O(n)
            # Какая-то операция, например, печать пары (arr[i], arr[j])
            pass

ИИ-помощник для собеседований

Хочешь уверенно проходить собеседования?

Попробуй ИИ-помощник для собеседований: слышит вас и собеседника, анализирует экран, подсказывает ответы в реальном времени, работает без VPN и не попадает в захват экрана.

Подробнее