Ответ
Частая ошибка — не учитывать сложность операций внутри цикла, что приводит к некорректной общей оценке.
Пример 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²).
Ответ 18+ 🔞
А, слушай, вот это вообще классика, блядь! Люди ж как думают? Цикл по массиву — значит O(n), и всё, пиздец, задача решена. А потом приходит массив на десять тыщ элементов, и приложение накрывается медным тазом, а они сидят и чешут репу: «Ну что за хуйня, на айфоне шестом тормозит?»
Смотри, вот тебе прямо учебник по тому, как на ровном месте наделать 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 растёт с каждой итерацией!
result.append(element)
}
}
return result
// Итого: O(n * m) → а в худшем случае, когда все элементы уникальны, это O(n²), ядрёна вошь!
}В чём подвох, блядь? Ну, цикл-то O(n), это каждый дурак скажет. А вот contains для массива — это же линейный поиск, ёпта! Он каждый раз пробегает по всему текущему result. Сначала там 0 элементов, потом 1, потом 2... и так до n. В сумме получается не O(n), а 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²), потому что строка — неизменяемая сука, и каждый `+=` копирует её целиком!
}Вот это вообще шедевр, блядь. Человек думает: «Я ж просто буквы добавляю». А на деле, каждый раз, когда ты делаешь result += word, система берёт ВСЮ старую строку result, копирует её в новое место, добавляет word и выкидывает старую. Представь, ты собрал строку в 10 тысяч символов и добавляешь слово «привет». Скопировать 10 тысяч символов — это O(k), ёпта! И так на каждой итерации. Пиздец и ужас.
А вот как надо, блядь, чтобы не было мучительно больно:
// Хорошее решение: O(n) с использованием Set. Он ищет за O(1), ёбана в рот!
func removeDuplicatesGood<T: Hashable>(from array: [T]) -> [T] {
var seen = Set<T>() // Волшебная структура, поиск в среднем 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), потому что умные дядьки в Apple уже всё придумали.
func buildStringGood(from words: [String]) -> String {
return words.joined() // Использует внутренний буфер и не копирует всё каждый раз, хитрая жопа!
}Вывод, блядь, который надо выжечь себе на подкорке: Нельзя смотреть только на внешний цикл. Надо смотреть, что ты делаешь ВНУТРИ него на каждой итерации. Если внутри есть contains по массиву, first(where:), insert(at: 0) или конкатенация строк — это почти наверняка O(n), которое, будучи внутри другого O(n), даёт тебе O(n²). И тогда твоё приложение начинает бздеть и тормозить на больших данных, а ты остаёшься в полном, блядь, недоумении. Думай головой, э бошка!