Алгоритмы

Junior

Суть

Алгоритм — конечная последовательность шагов, превращающая входные данные в выходные. Один и тот же алгоритм можно записать на любом языке; на собеседовании важна не запись, а умение оценить, как растёт время и память с ростом входа.

Асимптотические обозначения — здесь чаще всего ошибаются

• O(f(n)) — верхняя граница: алгоритм работает не медленнее f(n).
• Ω(f(n)) — нижняя граница: не быстрее f(n).
• Θ(f(n)) — точная оценка, когда верхняя и нижняя границы совпадают.

Худший, лучший и средний случаи — другое измерение. Каждый из них можно описать любой из трёх нотаций. Например, у быстрой сортировки худший случай Θ(n²), средний — Θ(n log n). На практике говорят «O(...)» и подразумевают худший или средний случай — уточняйте, какой.

Константы и младшие члены отбрасываются: 3n² + 100n — это O(n²). O(1) означает, что время не зависит от размера входа — цикл из фиксированных десяти итераций тоже O(1).

Типичные классы

• O(1) — доступ по индексу, поиск в Dictionary/Set.
• O(log n) — бинарный поиск в отсортированном массиве.
• O(n) — линейный проход, Array.contains, String.count.
• O(n log n) — sort() / sorted() (с Swift 5 — стабильная сортировка на основе Timsort).
• O(n²) — вложенные циклы по тем же данным.

func binarySearch(_ a: [Int], _ target: Int) -> Int? {
    var lo = 0, hi = a.count - 1
    while lo <= hi {                      // каждый шаг делит диапазон пополам
        let mid = (lo + hi) / 2
        if a[mid] == target { return mid }
        if a[mid] < target { lo = mid + 1 } else { hi = mid - 1 }
    }
    return nil
}
print(binarySearch([1, 3, 5, 7, 9], 7) as Any)   // Optional(3)

// O(n²): для каждого элемента ищем дубликат линейно
func hasDuplicateSlow(_ a: [Int]) -> Bool {
    for i in a.indices {
        for j in a.indices where j != i && a[i] == a[j] { return true }
    }
    return false
}

// O(n): Set.insert сообщает, был ли элемент уже внутри
func hasDuplicate(_ a: [Int]) -> Bool {
    var seen = Set<Int>()
    return a.contains { !seen.insert($0).inserted }
}

Пространственная сложность и рекурсия

Память оценивают так же: hasDuplicate тратит O(n) на Set, hasDuplicateSlow — O(1). Рекурсия стоит O(глубины) стека; Swift не гарантирует оптимизацию хвостовой рекурсии, поэтому глубокая рекурсия (десятки тысяч уровней) на iOS роняет приложение — заменяйте циклом.

На что смотрит интервьюер

• Вы сначала называете сложность своего решения, а потом предлагаете, как её улучшить (обычно: хеш-таблица вместо вложенного цикла).
• Вы знаете сложности стандартных операций Swift, а не только «учебниковые» структуры.