Что такое сложность алгоритма

Question

Что такое сложность алгоритма

Тип вопроса: Алгоритмы и структуры данных Вероятность: 23% Категория: Android Разработчик

Ответ

Сложность алгоритма — это оценка количества ресурсов (времени/памяти), которые потребуются для его выполнения, в зависимости от размера входных данных.

Основные виды:

O(1) – константная (доступ по индексу в массиве)
O(n) – линейная (поиск в неотсортированном массиве)
O(log n) – логарифмическая (бинарный поиск)
O(n²) – квадратичная (пузырьковая сортировка)

// O(n) – линейный поиск
fun linearSearch(list: List<Int>, target: Int): Int? {
    for (i in list.indices) {
        if (list[i] == target) return i
    }
    return null
}

Нюансы:

Анализируется худший случай (Big-O)
Константы и меньшие степени игнорируются (O(2n) → O(n))
Влияет на производительность при больших данных

Ответ 18+ 🔞

А, ну это ж классика, ебать мои старые костыли! Сложность алгоритма — это, по сути, ответ на вопрос: «Ну и насколько этот твой код будет тормозить, когда данных станет овердохуища?»

Представь, что у тебя есть задача и ты её решаешь. Можно решать тупо, в лоб, а можно — с хитрой жопой. Вот эта самая «сложность» и показывает, как быстро твоё решение упрётся в потолок, когда информации станет реально много. Измеряется она обычно во времени (сколько шагов процессор наделает) или в памяти (сколько оперативки сожрёт).

Основные виды, которые надо знать, чтобы не выглядеть полным ебанько:

O(1) – Константная. Вообще похуй, сколько данных. Время одно и то же. Как достать пиво из холодильника — открыл дверцу, взял. Не важно, одно пиво там или сто. Как доступ к элементу массива по индексу: list[42] — и всё, хуй с горы, ты его уже получил.
O(n) – Линейная. Вот тут уже зависит. Если данных в n раз больше, то и времени нужно примерно в n раз больше. Как найти свою зачётку в стопке других: просматриваешь каждую по очереди, пока не найдёшь свою. Чем толще стопка, тем дольше искать.
O(log n) – Логарифмическая. Это уже магия, чувак. Время растёт ооочень медленно. Классика — бинарный поиск. Ты берёшь отсортированный список, смотришь на середину, отбрасываешь половину, где заведомо нет твоего элемента, и повторяешь. Это как искать слово в толстом словаре — открыл примерно на нужной букве, понял, надо листать вперёд или назад, и так быстро сужаешь круг. Эффективно, пиздец.
O(n²) – Квадратичная. Вот это уже пиздец, товарищ. Время растёт как квадрат от количества данных. Типичный пример — тупая пузырьковая сортировка, где ты для каждого элемента пробегаешься по всему списку. Если элементов 1000, то операций будет около миллиона. Если 10000 — уже сто миллионов. Чувствуешь разгон? Доверия к такому алгоритму — ебать ноль.

// O(n) – линейный поиск. Просто тупо перебираем, пока не найдём.
fun linearSearch(list: List<Int>, target: Int): Int? {
    for (i in list.indices) {
        if (list[i] == target) return i // Нашли — ура, выходим.
    }
    return null // Прошли всё — нихуя нет.
}

Важные нюансы, а то будешь выглядеть как мартышлюшка:

Считают обычно худший случай (Big-O). Потому что оптимист на тонущем корабле — это, блядь, плохой оптимист. Надо понимать, насколько всё может максимально охереть.
Константы — похуй. Если у тебя алгоритм делает 2n или 200n шагов — всё равно записывается как O(n). Потому что когда n станет миллионом, разница между миллионом и двумя миллионами шагов — это детский лепет на фоне общей хуйни. Главная тенденция — линейный рост.
Меньшие степени — тоже похуй. O(n² + n) — это по факту O(n²), потому что когда n большое, член n² задаёт тон, а n рядом с ним — просто нищеброд.
И да, это всё реально влияет. Можно написать код, который на десяти элементах работает мгновенно, а на десяти тысячах — накрывается медным тазом и заставляет пользователя думать, что комп сдох. Понимание сложности помогает этого избежать.