Ответ
Основные классы алгоритмической сложности в порядке возрастания эффективности (от лучшей к худшей) выглядят так:
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)
Объяснение и примеры на Go
1. O(1) — Константное время Время выполнения не зависит от размера входных данных.
// Получение элемента из слайса по индексу
// не зависит от количества элементов в `arr`.
func getFirstElement(arr []int) int {
if len(arr) == 0 {
return -1 // или вернуть ошибку
}
return arr[0]
}2. O(log n) — Логарифмическое время Время выполнения растет логарифмически с увеличением размера данных. Обычно это алгоритмы, которые на каждом шаге отбрасывают половину данных.
// Бинарный поиск в отсортированном массиве.
func binarySearch(arr []int, target int) bool {
low, high := 0, len(arr)-1
for low <= high {
mid := low + (high-low)/2 // Безопасное вычисление середины
if arr[mid] == target {
return true
}
if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return false
}3. O(n) — Линейное время Время выполнения прямо пропорционально размеру входных данных. Алгоритму нужно "просмотреть" каждый элемент один раз.
// Линейный поиск элемента в массиве.
func findValue(arr []int, target int) bool {
for _, v := range arr {
if v == target {
return true
}
}
return false
}4. O(n log n) — Линейно-логарифмическое время Это "золотой стандарт" для алгоритмов сортировки, основанных на сравнениях. Примеры: сортировка слиянием (Merge Sort), быстрая сортировка (Quick Sort).
// В стандартной библиотеке Go функция sort.Ints
// использует гибридный алгоритм (IntroSort),
// который в среднем имеет сложность O(n log n).
import "sort"
func sortArray(arr []int) {
sort.Ints(arr)
}5. O(n²) — Квадратичное время Время выполнения растет пропорционально квадрату размера данных. Часто встречается во вложенных циклах, где оба цикла итерируются по одному и тому же набору данных.
// Проверка на наличие дубликатов с помощью вложенных циклов.
func hasDuplicates(arr []int) bool {
n := len(arr)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if arr[i] == arr[j] {
return true
}
}
}
return false
}6. O(2ⁿ) — Экспоненциальное время
Время выполнения удваивается с каждым новым элементом. Такие алгоритмы очень медленные и применимы только для малых n. Пример: рекурсивное вычисление чисел Фибоначчи без мемоизации.
7. O(n!) — Факториальное время Время выполнения растет с факториальной скоростью. Это самые медленные алгоритмы. Пример: решение задачи коммивояжера методом полного перебора всех возможных маршрутов.
Ответ 18+ 🔞
Так, слушай сюда, дружище, раз уж ты решил влезть в эту кашу под названием «алгоритмическая сложность». Это, блядь, как сортировка носков в комоде — если делать в лоб, то заебёшься на всю оставшуюся жизнь, а если с умом — то за пять минут управишься. Вот тебе вся эта иерархия, от боженьки до полного пиздеца, разжёванная на примерах из Го, чтобы не было мучительно больно.
Вот они, эти святые градации, от самой быстрой до той, от которой хочется повеситься: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)
Разбор полётов, или Почему твой код тормозит как старая «копейка»
1. O(1) — Константное время (Святость) Это когда тебе похуй, сколько там данных. Ты делаешь одно действие, и всё. Как взять первую бутылку пива из холодильника — неважно, их там три или триста.
// Достаём первый элемент из слайса. Хоть один элемент, хоть овердохуища.
func getFirstElement(arr []int) int {
if len(arr) == 0 {
return -1 // Ну нету, и хуй с ним
}
return arr[0] // Взял и пошёл. Красота.
}2. O(log n) — Логарифмическое время (Умный поиск) Это как искать слово в толстом словаре. Ты не листаешь всё подряд, а открываешь посередине, смотришь — не то, и отбрасываешь половину страниц. С каждым шагом задача уменьшается вдвое. Хитро, блядь.
// Бинарный поиск. Отсортированный массив — наше всё.
func binarySearch(arr []int, target int) bool {
low, high := 0, len(arr)-1
for low <= high {
mid := low + (high-low)/2 // Чтобы не вылезти за пределы, умник
if arr[mid] == target {
return true // Нашёл, сука!
}
if arr[mid] < target {
low = mid + 1 // Ищем справа
} else {
high = mid - 1 // Ищем слева
}
}
return false // Нету, пиздец.
}3. O(n) — Линейное время (Честный работяга) Тут всё просто: чем больше данных, тем дольше работаешь. Пропорционально. Как проверять, не забыл ли ты ключи в каждой куртке в прихожей. Одна куртка — одна проверка. Десять курток — десять проверок.
// Линейный поиск. Тупо смотрим каждый элемент.
func findValue(arr []int, target int) bool {
for _, v := range arr {
if v == target {
return true // Ура, нашёл!
}
}
return false // Проебал.
}4. O(n log n) — Линейно-логарифмическое время (Золотая середина сортировок) Это аристократия среди алгоритмов. Так работают все уважающие себя алгоритмы сортировки, основанные на сравнениях. Быстрая, слиянием — они все тут. Это как разложить колоду карт по мастям и достоинствам — быстро и эффективно.
// Стандартная сортировка в Go. Не еби мозг, используй готовое.
import "sort"
func sortArray(arr []int) {
sort.Ints(arr) // Внутри там магия, но сложность O(n log n)
}5. O(n²) — Квадратичное время (Тупой перебор) Вот здесь начинается пиздец. Это когда ты для каждой куртки проверяешь, не оставил ли ты ключи в каждой другой куртке. Два вложенных цикла по одним и тем же данным. На маленьких объёмах ещё куда ни шло, а на тысяче элементов — это уже самоубийство.
// Поиск дубликатов тупым методом. В лоб, блядь.
func hasDuplicates(arr []int) bool {
n := len(arr)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ { // Для каждого i пробегаем по всему хвосту
if arr[i] == arr[j] {
return true // О, бля, нашли одинаковые!
}
}
}
return false
}6. O(2ⁿ) — Экспоненциальное время (Начинается ад) Тут время выполнения удваивается с каждым новым элементом. Это как рекурсивно вычислять числа Фибоначчи без мемоизации. Для n=40 это уже пиздец какой долгий процесс. Используй только если готов ждать до второго пришествия.
7. O(n!) — Факториальное время (Апокалипсис) Абсолютный пиздец. Самые медленные алгоритмы. Это как перебирать ВСЕ возможные маршруты для коммивояжёра, чтобы найти самый короткий. Даже для n=15 это уже астрономическое число операций. Если видишь такую сложность в своём коде — беги, блядь, переписывай всё, пока не поздно.
Вот и вся недолгая история. Запоминай эту иерархию, как «Отче наш», и не пиши квадратичные алгоритмы на больших данных, а то получишь по ебалу от продакшена.