Приведи пример плохой оценки сложности алгоритма

Пример плохой оценки сложности алгоритма

Одним из классических примеров плохой оценки сложности — это неучёт реальных ограничений и контекста, когда формальная асимптотическая оценка не отражает фактическую производительность. Рассмотрим задачу поиска k наименьших элементов в несортированном массиве.

Наивный подход с сортировкой

func findKSmallestPoorly(_ array: [Int], _ k: Int) -> [Int] {
    // Копируем массив чтобы не менять оригинал
    var sorted = array
    // Используем встроенную сортировку
    sorted.sort()
    // Возвращаем первые k элементов
    return Array(sorted.prefix(k))
}

Формальная оценка: O(n log n), где n — размер массива. Кажется приемлемо для многих случаев.

Почему это плохая оценка на практике?

1. Неучёт размера k относительно n

   • Если k = 3, а n = 1_000_000, нам не нужно сортировать весь массив
   • Лучше использовать алгоритм QuickSelect со средней сложностью O(n)

2. Игнорирование констант и накладных расходов

   // QuickSelect реализация
   func findKSmallestBetter(_ array: [Int], _ k: Int) -> [Int] {
       var arr = array
       func quickSelect(_ left: Int, _ right: Int) -> Int {
           let pivotIndex = partition(left, right)
           if pivotIndex == k { return pivotIndex }
           return pivotIndex < k ? 
               quickSelect(pivotIndex + 1, right) : 
               quickSelect(left, pivotIndex - 1)
       }
       // ... реализация partition
       let index = quickSelect(0, arr.count - 1)
       return Array(arr[..<min(k, arr.count)])
   }
   

   Хотя формально QuickSelect тоже O(n) в среднем, его константы могут быть выше при малых n

3. Пренебрежение характеристиками данных

   • Для почти отсортированных данных сортировка вставками может быть быстрее
   • При маленьких n (n < 50) простые алгоритмы часто outperform сложные

4. Неучёт требований к памяти

   // Ещё худший пример — рекурсия без оптимизации
   func fibonacciNaive(_ n: Int) -> Int {
       guard n > 1 else { return n }
       return fibonacciNaive(n - 1) + fibonacciNaive(n - 2)
   }
   

   Сложность: O(2^n) — экспоненциальный рост, хотя задачу можно решить за O(n) с O(1) памяти

Ключевые ошибки в оценке

• Абстрагирование от реальных данных: O(n log n) сортировки может быть хуже O(n²) для n ≤ 10
• Игнорирование cache locality: Линейный проход по массиву часто быстрее "оптимальных" алгоритмов
• Неучёт parallelism: Некоторые O(n log n) алгоритмы лучше параллелятся чем O(n)
• Пренебрежение worst-case: QuickSelect имеет O(n²) в худшем случае, что неприемлемо для реальных систем

Правильный подход к оценке

// Адаптивный выбор алгоритма
func findKSmallestAdaptive(_ array: [Int], _ k: Int) -> [Int] {
    let n = array.count
    
    switch (n, k) {
    case (..<50, _):
        // Для маленьких массивов — insertion sort
        return array.sorted().prefix(k).map { $0 }
        
    case (_, ..<10) where n > 1000:
        // Для очень маленьких k — heap-based подход
        var heap = Array(array.prefix(k))
        // ... обработка остальных элементов
        
    default:
        // В общем случае — QuickSelect с защитой от worst-case
        return findKSmallestBetter(array, k)
    }
}

Вывод: Плохая оценка сложности возникает когда:

1. Рассматривается только асимптотика без учёта констант
2. Игнорируются характеристики входных данных
3. Не учитываются требования к памяти и реальные ограничения железа
4. Выбирается алгоритм исходя только из формальной сложности, без benchmarking на типичных данных

Для iOS разработки особенно важно учитывать:

• Ограничения мобильных устройств по памяти и CPU
• Типичные размеры данных в мобильных приложениях
• Требования к отзывчивости UI (алгоритмы должны быть прерываемыми)