Ответ
O(1) – константная сложность. Время выполнения не зависит от размера входных данных.
Пример: доступ к элементу массива по индексу.
const arr = [1, 2, 3];
console.log(arr[0]); // O(1)O(n) – линейная сложность. Время растёт пропорционально размеру входных данных.
Пример: перебор массива.
for (let i = 0; i < arr.length; i++) { // O(n)
console.log(arr[i]);
}O(log n) – логарифмическая сложность. Время растёт логарифмически (например, бинарный поиск).
O(n²) – квадратичная сложность. Время растёт квадратично (например, вложенные циклы).
for (let i = 0; i < n; i++) { // O(n²)
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}O(2ⁿ) – экспоненциальная сложность. Время удваивается с каждым увеличением входных данных (например, рекурсивный Фибоначчи без мемоизации).
O(n!) – факториальная сложность. Наихудший случай (например, перебор всех перестановок).
Ответ 18+ 🔞
А, вот эта тема про сложность алгоритмов! Ну что ж, давай разберёмся, пока твой процессор не накрылся медным тазом от наших размышлений.
Смотри, есть у нас такая штука — O(1). Это как вломиться в свой холодильник за пивом. Неважно, сколько там всего наставлено, ты сразу знаешь, где оно лежит. Время одно и то же, хоть десять банок, хоть сто. Константа, ёпта.
const arr = [1, 2, 3];
console.log(arr[0]); // O(1) — взял и вынул, без вопросов.Дальше — O(n). Линейная, блядь. Это как если тебе сказали: «Найди в этом чулане один чёрный носок». А там — пиздец какой бардак, и носок может быть в самом низу. Чем больше хлама в чулане (n), тем дольше ты будешь копаться. Прямая зависимость, ничего личного.
for (let i = 0; i < arr.length; i++) { // O(n)
console.log(arr[i]); // Перебираем всё подряд, как честный идиот.
}А вот O(log n) — это уже хитрая жопа. Логарифмическая. Представь, что у тебя телефонная книга на тысячу страниц. Ты открываешь её посередине, смотришь — «М». Тебе надо «С». Ты отбрасываешь всю левую половину и снова рвёшь оставшуюся пополам. И так пока не найдёшь. С каждым шагом задача уменьшается вдвое. Умно, да? Бинарный поиск, например.
O(n²) — это, сука, квадратичная. Настоящий ад для больших данных. Как если бы тебе надо было каждому человеку в толпе пожать руку каждому другому. Два вложенных цикла, блядь. Для десяти человек — сто рукопожатий. Для ста — уже десять тысяч. Чувствуешь, как всё замедляется? Пиздец, а не сложность.
for (let i = 0; i < n; i++) { // O(n²)
for (let j = 0; j < n; j++) {
console.log(i, j); // «Здравствуйте, я вас категорически ненавижу».
}
}O(2ⁿ) — экспоненциальная. Это когда твой код начинает ебать сам себя по рекурсии без мемоизации. Как задача про Ханойскую башню или нахождение всех подмножеств. Добавил один элемент — и время работы, блядь, УДВОИЛОСЬ. Добавил ещё один — УДВОИЛОСЬ СНОВА. Через пару десятков элементов вселенная остынет раньше, чем твой скрипт завершится.
И наконец, O(n!) — факториальная. Абсолютный пиздец, апогей страданий. Это перебор всех возможных перестановок. Например, «задача коммивояжёра» в лоб. Для 5 городов — 120 вариантов. Для 10 — уже 3.6 миллиона. Для 15 — 1.3 триллиона. Представь, твой комп пытается это посчитать... Да он взвоет, как сука, и сгорит к хуям собачьим.
Вот и вся недолгая история. Главное — понимать, что если ты пишешь вложенные циклы на овердохуища данных, то ты, прости, мудак. Думай головой, э бошка, выбирай правильные структуры и алгоритмы. А то будет тебе не O(1), а волнение ебать и терпения ноль.