Приведи пример алгоритма с неочевидной (плохо оцениваемой) временной сложностью.

Частая ошибка — не учитывать сложность операций внутри цикла, что приводит к некорректной общей оценке.

Пример 1: Использование contains внутри цикла по массиву

// Задача: Удалить дубликаты из массива.
// Плохое решение: O(n²)
func removeDuplicatesBad<T: Equatable>(from array: [T]) -> [T] {
    var result: [T] = []
    for element in array {               // O(n) итераций
        if !result.contains(element) {   // O(m) для каждого элемента, где m растет до n
            result.append(element)       // В среднем O(1)
        }
    }
    return result
    // Общая сложность: O(n * m) → в худшем случае O(n²)
}

Почему оценка плохая: Наивный разработчик может посчитать только внешний цикл O(n), забыв, что contains для массива — это линейный поиск O(m). В худшем случае (все элементы уникальны) m растет вместе с n.

Пример 2: Конкатенация строк в цикле

// Задача: Собрать строку из массива.
// Плохое решение: O(n²)
func buildStringBad(from words: [String]) -> String {
    var result = ""
    for word in words {          // O(n) итераций
        result += word           // O(k) где k — длина текущей строки `result`
    }
    return result
    // Общая сложность: O(n + k1 + k2 + ...) ~ O(n²), так как строка `result` постоянно копируется.
}

Исправление (хорошая оценка и эффективный алгоритм):

// Хорошее решение: O(n) с использованием Set для проверки уникальности.
func removeDuplicatesGood<T: Hashable>(from array: [T]) -> [T] {
    var seen = Set<T>()          // Поиск в Set в среднем O(1)
    var result: [T] = []
    for element in array {       // O(n) итераций
        if seen.insert(element).inserted { // O(1)
            result.append(element)         // O(1)
        }
    }
    return result
    // Общая сложность: O(n)
}

// Хорошее решение для строк: O(n)
func buildStringGood(from words: [String]) -> String {
    return words.joined() // Использует внутренний буфер для эффективной конкатенации.
}

Вывод: Всегда анализируйте сложность вложенных операций. Операции с массивами (contains, first, insert(at: 0)) часто имеют O(n), что в цикле дает O(n²).