Сложность алгоритмов. Как оценивать эффективность кода

Введение

Почти всегда существует способ проще и лучше, чем тот, что первым пришёл вам в голову. — Дональд Кнут

В мире разработки редко кто спорит о важности чистого кода, архитектуры и тестов. Но один из самых фундаментальных аспектов инженерного мышления нередко оказывается в тени — анализ сложности алгоритмов. Это не теоретическая абстракция, а практический инструмент, который помогает понять, насколько хорошо масштабируется ваш код, как он поведёт себя при увеличении объёма данных и где возникают узкие места.

Понимание сложности — это умение видеть не только, как работает алгоритм, но и как он ведёт себя в динамике. И если сегодня ваш код обрабатывает тысячи записей, а завтра — миллионы, именно анализ сложности определит, выдержит ли он этот рост.

Временная и пространственная сложность

Когда мы говорим об эффективности алгоритма, мы обычно имеем в виду две вещи:

• Временная сложность — как количество операций зависит от размера входных данных n;
• Пространственная сложность — сколько дополнительной памяти алгоритм требует по мере роста входных данных.

Обе метрики описывают не конкретные секунды или мегабайты, а зависимость от масштаба задачи. Это принципиально важно: мы не меряем скорость на конкретной машине, а анализируем поведение в пределе.

Асимптотический анализ и нотация Big O

Чтобы описывать эту зависимость, используется асимптотическая нотация, чаще всего — Big O.
Формально, запись O(f(n)) означает, что время выполнения алгоритма растёт не быстрее, чем функция f(n) при больших n.

Другими словами, Big O — это способ сказать: «если входные данные станут в 10 раз больше, насколько медленнее станет алгоритм».
Мы игнорируем конкретные коэффициенты и фокусируемся на темпе роста, потому что именно он определяет масштабируемость.

Лучший, средний и худший случаи

Сложность алгоритма может отличаться в зависимости от входных данных. Например, поиск элемента в отсортированном массиве может закончиться за одну операцию — или пройти весь массив. Поэтому различают:

• Лучший случай (best case) — когда всё складывается идеально;
• Средний случай (average case) — ожидаемое поведение на типичных данных;
• Худший случай (worst case) — гарантированный максимум затраченных ресурсов.

Именно худший случай чаще используется при анализе: он даёт верхнюю границу, обеспечивая предсказуемость.

Обзор ключевых классов сложности

Константная сложность — O(1)

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

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

метод Скрипт()
    КонстантнаяCложность()    
;

метод КонстантнаяCложность()
	знч Массив100 = ПолучитьМассивСлучайныхЧисел(10000)
	знч Массив10000 = ПолучитьМассивСлучайныхЧисел(1000000)
	    
	пер НачалоОперации = ДатаВремя.Сейчас()
	Массив100.Получить(50)
	пер ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()
	Консоль.Записать("Время доступа к элементу по индексу в массиве из 100 элементов: %{ДлительностьОперации} мс")
	
	НачалоОперации = ДатаВремя.Сейчас()
	Массив10000.Получить(5000)
	ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()
	Консоль.Записать("Время доступа к элементу по индексу в массиве из 10 000 элементов: %{ДлительностьОперации} мс")
;

Результат эксперимента:

Время доступа к элементу по индексу в массиве из 100 элементов: 1 мс  
Время доступа к элементу по индексу в массиве из 10 000 элементов: 1 мс  

Несмотря на то, что один массив в 100 раз больше другого, время доступа к элементу практически не изменилось. Это и есть поведение константной сложности.

Что это значит на уровне модели

Операция доступа по индексу (Массив.Получить(i)) в большинстве реализаций выполняется одинаково быстро, потому что:

1. Элементы массива хранятся в непрерывной области памяти.
2. Индексирование — это просто арифметика адресов: адрес нужного элемента вычисляется как базовый_адрес + (размер_элемента × индекс).

Процессор делает одно и то же количество шагов, независимо от размера массива.
Даже если массив состоит из миллиона элементов, вычисление позиции для 5000-го занимает те же наносекунды, что и для 5-го.

Константа не означает «моментально»

Важно понимать: O(1) не означает мгновенно. Это значит лишь, что время выполнения не растёт с увеличением n.
Операция может занимать 1 мс, 10 мс или даже секунду — но если она всегда занимает примерно одинаковое время, это всё ещё O(1).

Например, вызов кэшированной функции может быть O(1), но при этом медленным из-за задержек сети или ввода-вывода.
А вот поиск элемента в массиве без индексации, наоборот, будет O(n), даже если на малых данных кажется «почти мгновенным».

Где встречается константная сложность

Типичные операции O(1) включают:

• доступ к элементу по индексу (в массиве, списке фиксированного размера);
• проверка логического условия;
• присвоение переменной.

Константная сложность — это строительный кирпич эффективных алгоритмов.
Она сама по себе не гарантирует скорость всей программы, но если вы добились того, чтобы большинство критических операций выполнялись за O(1), значит, ваш код масштабируется предсказуемо и стабильно.

Константная сложность. Итог

Константная сложность — это не просто «быстро», это устойчиво.
Алгоритм с O(1) временем ведёт себя одинаково при 10 элементах и при миллионе.
И именно эта предсказуемость делает его базовым эталоном эффективности, на который равняются все остальные классы сложности.

---

Логарифмическая сложность — O(log n)

Логарифмическая сложность — один из наиболее «экономичных» классов роста. Она появляется в задачах, где на каждом шаге объём оставшейся работы уменьшается в несколько раз (обычно — пополам). Классический пример — бинарный поиск в отсортированном массиве: каждый шаг делит область поиска пополам, и уже через небольшое число шагов область становится тривиально маленькой.

Ниже — пример реализации бинарного поиска и демонстрация его использования.

метод Скрипт()
    ЛогарифмическаяCложность()    
;

метод ЛогарифмическаяCложность()   
    знч Массив100 = ПолучитьСортированныйМассивСлучайныхЧисел(КоличествоЭлементов = 100)
    знч Массив1000000 = ПолучитьСортированныйМассивСлучайныхЧисел(КоличествоЭлементов = 1000000)
    
    пер Результат = БинарныйПоискВМассиве(Массив100, Массив100.Получить(50))
    Консоль.Записать("Поиск по массиву 100 элементов. Индекс найденного элемента: %{Результат.Первый().Ключ}, количество итераций: %{Результат.Первый().Значение}")
    
    Результат = БинарныйПоискВМассиве(Массив1000000, Массив1000000.Получить(5000))
    Консоль.Записать("Поиск по массиву 1 000 000 элементов. Индекс найденного элемента: %{Результат.Первый().Ключ}, количество итераций: %{Результат.Первый().Значение}")  
;

метод БинарныйПоискВМассиве(МассивПоиска: Массив<Число>, ЗначениеПоиска: Число): Соответствие<Число, Число>
    пер ЛеваяГраницаПоиска = 0
    пер ПраваяГраницаПоиска = МассивПоиска.Граница()
    пер КоличествоИтераций = 0
    пока ЛеваяГраницаПоиска <= ПраваяГраницаПоиска
        КоличествоИтераций += 1
        пер СреднийЭлементИндекс = ((ЛеваяГраницаПоиска + ПраваяГраницаПоиска) / 2).ЦелаяЧасть() 
        знч СреднийЭлементЗначение = МассивПоиска.Получить(СреднийЭлементИндекс)
        если СреднийЭлементЗначение == ЗначениеПоиска
            возврат {СреднийЭлементИндекс: КоличествоИтераций}
        иначе если СреднийЭлементЗначение < ЗначениеПоиска
            ЛеваяГраницаПоиска = СреднийЭлементИндекс + 1
        иначе
            ПраваяГраницаПоиска = СреднийЭлементИндекс - 1
        ; 
    ;     
    возврат {-1: КоличествоИтераций} // Не нашли значение в массиве   
;

Почему это — O(log n)

Идея очень простая: на каждом шаге диапазон поиска сокращается примерно вдвое. Если изначально элементов n, то после одного шага остаётся ≈n/2, после двух — ≈n/4, после k шагов — ≈n / 2^k. Когда размер диапазона достигает 1, поиск заканчивается. Решая n / 2^k = 1 относительно k, получаем 2^k = n → k = log₂(n).

На практике для целого числа шагов в худшем случае число итераций будет примерно ⌊log₂(n)⌋ + 1 (в зависимости от реализации — +1 или без неё). Это значит: даже при очень большом n число шагов остаётся небольшим.

Конкретные числовые оценки (наглядно)

• Для n = 100:
  2^6 = 64, 2^7 = 128. Поскольку 64 < 100 ≤ 128, логарифм log₂(100) лежит между 6 и 7. Соответственно ⌊log₂(100)⌋ = 6, и в худшем случае потребуется 6 + 1 = 7 итераций.

• Для n = 1 000 000 (в коде второй массив создаётся с миллионным размером):
  2^10 = 1024. Тогда 2^20 = 1024 × 1024 = 1 048 576. Видно, что 2^19 = 524 288, а 2^20 = 1 048 576. Так как 524 288 < 1 000 000 ≤ 1 048 576, имеем ⌊log₂(1 000 000)⌋ = 19, и в худшем случае понадобится 19 + 1 = 20 итераций.

Эти числа иллюстрируют главный смысл O(log n): при увеличении n в тысячи или миллионы число итераций растёт очень слабо — логарифмически.

Детали реализации и важные замечания

• Требование сортировки. Бинарный поиск корректен только для отсортированных коллекций. Это фундамент: если массив не отсортирован, деление пополам утрачивает смысл.
• Итеративная vs рекурсивная реализация. Итеративная версия (как в примере) обычно требует O(1) дополнительной памяти; рекурсивная — O(log n) из-за стека вызовов.
• Лучший/средний/худший случаи.
  • Лучший случай: искомый элемент оказался в центральной позиции → O(1).
  • Худший/средний случаи: Θ(log n). При равновероятном распределении обычно подразумевают Θ(log n).
• База логарифма несущественна. В асимптотике base b у логарифма меняет только постоянный множитель: log_b(n) = log_k(n) / log_k(b). Константы игнорируются в записи O(...).

Где ещё встречается O(log n)

• Доступ/вставка/удаление в сбалансированных деревьях поиска (авл-деревья, красно-чёрные) — O(log n).
• Операции с приоритетной очередью на бинарной куче (heap) — вставка, извлечение минимума — O(log n).
• Некоторые шаги в алгоритмах поиска в графах при использовании сокращённых структур и индексирования — O(log n) за операцию.

Логарифмическая сложность — частый признак эффективных алгоритмов и структур данных, обеспечивающих баланс между скоростью работы и гибкостью.

Логарифмическая сложность. Итог

O(log n) — мощный и практичный класс сложности: операции растут очень медленно при увеличении данных. Бинарный поиск — наглядный и простой пример: деление области поиска пополам даёт гарантию, что число шагов пропорционально логарифму размера коллекции. Для инженерной практики важно помнить условия применимости (в частности, требование сортировки) и учитывать реализацию (итеративная/рекурсивная, защита от переполнения при расчёте среднего индекса). Логарифмические алгоритмы часто служат сердцем эффективных структур данных и остаются одним из базовых приёмов оптимизации.

---

Линейная сложность — O(n)

Если константная сложность (O(1)) — это «независимо от размера данных», то линейная сложность (O(n)) означает, что время выполнения растёт прямо пропорционально количеству элементов.
Каждый элемент обрабатывается хотя бы один раз, и общее время выполнения увеличивается вместе с объёмом входных данных.

Рассмотрим простой пример, который демонстрирует линейное поведение:

метод Скрипт()
	ЛинейнаяCложность()
;

метод ЛинейнаяCложность()
	знч Массив100000 = ПолучитьМассивСлучайныхЧисел(100000)
	знч Массив10000000 = ПолучитьМассивСлучайныхЧисел(10000000)
	
	пер НачалоОперации = ДатаВремя.Сейчас()
	пер СуммаЭлементов = ПолучитьСуммуЭлементовМассива(Массив100000)
	пер ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()
	Консоль.Записать("Время вычисления массив 100 000 элементов: %{ДлительностьОперации} мс. Результат: %{СуммаЭлементов}")
	
	НачалоОперации = ДатаВремя.Сейчас()
	СуммаЭлементов = ПолучитьСуммуЭлементовМассива(Массив10000000)
	ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()
	Консоль.Записать("Время вычисления массив 10 000 000 элементов: %{ДлительностьОперации} мс. Результат: %{СуммаЭлементов}")
;
	
метод ПолучитьСуммуЭлементовМассива(МассивЧисел: Массив): Число
	пер СуммаЭлементов = 0
	для Элемент из МассивЧисел
		СуммаЭлементов += Элемент
	;
	возврат СуммаЭлементов
;

Результат выполнения:

Время вычисления массив 100 000 элементов: 12 мс. Сумма всех элементов: 4996734023  
Время вычисления массив 10 000 000 элементов: 651 мс. Сумма всех элементов: 499983640264  

Рост объёма данных примерно в 100 раз приводит к увеличению времени выполнения примерно в 50–60 раз (что близко к линейной зависимости с поправкой на накладные расходы системы).

Почему это линейная сложность

Функция ПолучитьСуммуЭлементовМассива() проходит по каждому элементу массива ровно один раз, выполняя одно и то же простое действие — сложение.
Если элементов в массиве становится в два раза больше, то и сложений выполняется в два раза больше.
Формально это можно записать как:

T(n) = c * n

где c — это время на обработку одного элемента, а n — количество элементов.
Константа c зависит от конкретного оборудования и реализации, но сама зависимость линейна.

Линейная сложность на практике

Алгоритмы с O(n) — это рабочие лошадки любой системы.
Они не идеальны, но надёжны и предсказуемы.
Типичные примеры:

• обход массива, списка, коллекции;
• фильтрация, подсчёт, проверка условий;
• линейный поиск элемента без индексации;
• простая агрегация данных (например, вычисление суммы или среднего).

Такие алгоритмы масштабируются достаточно хорошо:
увеличение объёма данных в 10 раз увеличивает время работы примерно в 10 раз — никаких сюрпризов.

Важное уточнение: линейная не значит «быстрая»

Иногда можно услышать: «O(n) — это нормально, значит быстро». Не всегда.
Если n — это десятки или сотни миллионов записей, даже линейный проход займёт секунды или минуты.
Здесь важно помнить, что асимптотика описывает характер роста, но не абсолютное время.

Кроме того, иногда линейные операции встраиваются друг в друга, создавая эффект O(n²) — например, когда для каждого элемента выполняется ещё один линейный поиск.

Линейная сложность. Итог

Линейная сложность — это золотая середина между простотой и масштабируемостью.
Алгоритмы O(n) легко читать, легко прогнозировать и, при разумных размерах данных, дают приемлемую производительность.
Но важно помнить: каждая операция на каждом элементе имеет свою цену — и в больших системах именно сумма этих «маленьких» действий определяет скорость всего приложения.

---

Линейно-логарифмическая сложность — O(n log n)

Когда говорят, что алгоритм «масштабируется хорошо», чаще всего имеют в виду именно линейно-логарифмическую сложность.
Это разумный компромисс между скоростью и универсальностью. Такие алгоритмы растут немного быстрее линейных, но всё ещё намного медленнее квадратичных, что делает их эффективными при работе с большими объёмами данных. Типичный представитель этого класса — сортировка слиянием (Merge Sort).

Приведённый ниже пример демонстрирует работу алгоритма слияния и рекурсивного разбиения массива:

метод Слить(ЛевыйМассив: Массив<Число>, ПравыйМассив: Массив<Число>): Массив<Число>
    
    знч Результат = <Число>[]
    пер ИндексЛевый = 0
    пер ИндексПравый = 0
    
    // Проходим оба массива, пока оба не закончились
    пока (ИндексЛевый < ЛевыйМассив.Размер() и ИндексПравый < ПравыйМассив.Размер())
        если (ЛевыйМассив[ИндексЛевый] <= ПравыйМассив[ИндексПравый])
            Результат.Добавить(ЛевыйМассив[ИндексЛевый])
            ИндексЛевый += 1
        иначе
            Результат.Добавить(ПравыйМассив[ИндексПравый])
            ИндексПравый += 1
        ;
    ;

    // Добавляем оставшиеся элементы левого массива
    пока (ИндексЛевый < ЛевыйМассив.Размер())
        Результат.Добавить(ЛевыйМассив[ИндексЛевый])
        ИндексЛевый += 1
    ;

    // Добавляем оставшиеся элементы правого массива
    пока (ИндексПравый < ПравыйМассив.Размер())
        Результат.Добавить(ПравыйМассив[ИндексПравый])
        ИндексПравый += 1
    ;

    возврат Результат
;

// Рекурсивная функция сортировки слиянием
метод СортировкаСлиянием(ИсходныйМассив: Массив<Число>): Массив<Число>
    если (ИсходныйМассив.Размер() <= 1) 
        возврат ИсходныйМассив
    ;

    пер СерединаМассива = (ИсходныйМассив.Размер() / 2).ЦелаяЧасть()
    знч ЛевыйМассив = СортировкаСлиянием(ИсходныйМассив.ПодМассив(0, СерединаМассива))
    знч ПравыйМассив = СортировкаСлиянием(ИсходныйМассив.ПодМассив(СерединаМассива))

    возврат Слить(ЛевыйМассив, ПравыйМассив)
;

метод Скрипт()
    
    пер НачалоОперации = ДатаВремя.Сейчас()
    знч ИсходныйМассив10 = ПолучитьМассивСлучайныхЧисел(10)
    знч ОтсортированныйМассив10 = СортировкаСлиянием(ИсходныйМассив10)
    пер ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()  
    Консоль.Записать("Отсортированный массив: %ОтсортированныйМассив10") 
    Консоль.Записать("Длительность: %ДлительностьОперации мс")
    
    НачалоОперации = ДатаВремя.Сейчас()
    знч ИсходныйМассив1000 = ПолучитьМассивСлучайныхЧисел(1000)
    знч ОтсортированныйМассив1000 = СортировкаСлиянием(ИсходныйМассив1000)
    ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах()  
    Консоль.Записать("Отсортированный массив: %{ОтсортированныйМассив1000.Представление().Обрезать(50,"...]")}")
    Консоль.Записать("Длительность: %ДлительностьОперации мс") 
;

Результат выполнения:

Отсортированный массив: [320, 1794, 1853, 2173, 2796, 5968, 6504, 8968, 9516, 9993], Длительность: 6 мс  
Отсортированный массив: [7, 13, 20, 24, 35, 35, 36, 73, 85, 89, 93, 97...], Длительность: 46 мс  

Даже при увеличении размера массива в 100 раз, время выросло меньше чем в 10 раз — поведение, характерное именно для O(n log n).

Как работает сортировка слиянием

Сортировка слиянием (merge sort) основана на двух идеях:

1. Разделяй — рекурсивно делим массив пополам, пока не останутся массивы длиной 1.
2. Властвуй — постепенно объединяем отсортированные части, используя метод Слить().

На каждом уровне рекурсии мы выполняем линейный проход по данным (O(n)), а число уровней разбиений составляет log₂(n) — потому что на каждом шаге массив делится пополам.

В результате получаем общую формулу:

T(n) = n × log₂(n)

Почему O(n log n) быстрее, чем O(n²)

На первый взгляд, log n — незначительная добавка, но разница колоссальная.
Например:

• для n = 1 000, log₂(n) ≈ 10 → n log n ≈ 10 000;
• для n = 1 000, n² = 1 000 000.

Разница — в сотни раз.
Поэтому O(n log n) — это реалистический предел скорости для алгоритмов сортировки на основе сравнений (merge sort, quick sort, heap sort и др.).

Что делает слияние линейно-логарифмическим

Каждое слияние (Слить()) само по себе работает за O(n) — оно просто проходит по обоим массивам, добавляя элементы по порядку.
Но из-за рекурсивного деления мы выполняем такие слияния на каждом уровне дерева вызовов:

• На первом уровне — 1 слияние длиной n;
• На втором — 2 слияния длиной n/2;
• На третьем — 4 слияния длиной n/4;
• … и так далее.

Если сложить все уровни, общее количество операций даёт n × log n.

Пространственная сложность

Сортировка слиянием требует дополнительной памяти для хранения временных массивов (результатов слияний).
Поэтому пространственная сложность — O(n).
Это одна из причин, почему на практике иногда выбирают другой алгоритм сортировки - QuickSort: он тоже O(n log n), но может работать почти без дополнительной памяти.

Практическая значимость

O(n log n) — это оптимум для большинства реальных задач, где требуется упорядочивание, группировка или сведение данных.
Линейные алгоритмы быстрее, но они применимы только к уже отсортированным структурам.
А всё, что медленнее O(n log n), быстро перестаёт быть применимым при больших объёмах.

Почему O(n log n) — практический предел сортировки

Существует доказательство, что ни один алгоритм сортировки на основе сравнений не может быть быстрее O(n log n) в худшем случае. Это связано с количеством возможных перестановок и структурой бинарного дерева решений.
Чтобы обойти этот предел, нужно изменить саму модель — например, использовать не сравнения, а разрядный анализ (как в radix sort), что возможно не для всех типов данных.

Линейно-логарифмическая сложность. Итог

Линейно-логарифмическая сложность — это компромисс между вычислительными затратами и гибкостью применения.
Она отражает идею «делить и властвовать»: уменьшать задачу на каждом шаге, сохраняя общее количество операций разумным.
Сортировка слиянием — классический пример того, как инженерная элегантность превращается в асимптотическую эффективность.

---

Квадратичная сложность — O(n²)

Квадратичная сложность означает, что количество операций растёт пропорционально квадрату размера входных данных. Проще говоря: если вы увеличите n в 10 раз, время работы (в худшем приближении) вырастет примерно в 10² = 100 раз. Такие алгоритмы быстро становятся непрактичными при росте объёма данных — поэтому важно уметь их распознавать, оценивать и по возможности заменять.

Приведённый ниже пример демонстрирует работу алгоритма пузырьковой сортировки массива Как работает пузырьковая сортировка:

• Проходим по массиву много раз.
• На каждом проходе сравниваем соседние элементы.
• Если левый > правого — меняем их местами.
• После первого прохода самое большое число «всплывает» в конец (как пузырёк).
• На следующем проходе уже не трогаем последний элемент — он уже на месте.
• И так далее.

метод Скрипт()
    КвадратичнаяCложность()    
; 

метод КвадратичнаяCложность()
    знч Массив100 = ПолучитьМассивСлучайныхЧисел(100)
    знч Массив1000 = ПолучитьМассивСлучайныхЧисел(1000)
    
    пер НачалоОперации = ДатаВремя.Сейчас()
    пер КоличествоИтераций = СортировкаПузырьком(Массив100)
    пер ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах() 
    Консоль.Записать("Время сортировки массива 100 элементов: %{ДлительностьОперации} мс. Количество итераций: %{КоличествоИтераций}")
    
    НачалоОперации = ДатаВремя.Сейчас()
    КоличествоИтераций = СортировкаПузырьком(Массив1000)
    ДлительностьОперации = (ДатаВремя.Сейчас() - НачалоОперации).ВМиллисекундах() 
    Консоль.Записать("Время сортировки массива 1000 элементов: %{ДлительностьОперации} мс. Количество итераций: %{КоличествоИтераций}")     
;

метод СортировкаПузырьком(ИсходныйМассив: Массив<Число>): Число
    пер ДлинаМассива = ИсходныйМассив.Граница()
    пер КоличествоИтераций = 0
    для i = 0 по ДлинаМассива - 1
	    // Внутренний цикл: до (n - 1 - i), потому что конец уже отсортирован
        для j = 0 по (ДлинаМассива - 1 - i) 
            КоличествоИтераций += 1
            если (ИсходныйМассив[j] > ИсходныйМассив[j + 1]) 
                // Меняем элементы местами (деструктуризация)
                знч temp = ИсходныйМассив[j]
                ИсходныйМассив[j] = ИсходныйМассив[j + 1]
                ИсходныйМассив[j + 1] = temp
            ;
        ;    
    ;
    Консоль.Записать(ИсходныйМассив.Представление().Обрезать(100, "...")) 
    возврат КоличествоИтераций          
;

Результат выполнения:

Время сортировки массива 100 элементов: 15 мс. Количество итераций: 4950
Время сортировки массива 1000 элементов: 301 мс. Количество итераций: 499500  

Откуда берутся количество итераций

Во вложенных циклах (внешний индекс i, внутренний j) внутренняя итерация выполняется n - i - 1 раз при каждом i. Общее число итераций (парных сравнений) равно сумме

Посчитаем для n:

• для n = 100: 100 * 99 = 9900 → 9900 / 2 = 4950.
• для n = 1000: 1000 * 999 = 999000 → 999000 / 2 = 499500.

Как меняются итерации при росте n

Отношение количества итераций:

То есть при увеличении n в 10 раз число сравнений выросло примерно в ~101 раз — близко к ожидаемому квадратичному росту (≈100×).

Почему время выросло не так, как количество итерации

Мы наблюдаем: 15 → 301 мс, то есть время выросло в ~20 раз:

Это не противоречит асимптотике — O(n²) описывает поведение при больших n, но не гарантирует точной кратности времени числу итераций. Причины рассогласования:

• Константы и накладные расходы. Асинхронная работа среды выполнения, накладные расходы на вызовы методов (например, Получить() вместо прямого индексирования), проверка границ, и т. п. — всё это даёт фиксированную добавку к времени, которую при малых n видно сильнее.
• Различия в количестве операций внутри итерации. Количество обменов может отличаться для двух массивов, и обмены чаще дороже сравнений.
• Кэш, предсказание ветвлений, CPU-частоты. На больших массивах поведение кеша памяти и предсказание ветвлений меняется; иногда это помогает (лучшее использование последовательного прохода в памяти), иногда мешает.
• Разрешение и шум измерения. Для коротких замеров погрешность таймера и другие фоновые процессы ОС влияют сильнее.

Итог: итерации показывают идею роста (~n²), а время — реальное поведение, где константы и оборудование решают, насколько близко результаты к этой теоретической кривой.

Типичные свойства пузырьковой сортировки и O(n²)

• Худший и средний случаи: O(n²) — для случайно упорядоченных и обратных массивов.
• Лучший случай: Если реализован «ранний выход» (break, когда на проходе не было обменов), пузырёк даёт O(n) на уже отсортированных данных. Без этой оптимизации лучший случай тоже O(n²).
• Количество сравнений и обменов: примерно ~n²/2 сравнений; обменов — от 0 (если уже отсортирован) до ~n²/2 (в худшем случае).

Как распознать O(n²) в коде

• Вложенные циклы.
• Перебор всех пар элементов (все сочетания, все перестановки пар).
• Наивные проверки уникальности/пары без использования предварительной сортировки.

Когда O(n²) приемлема, а когда нет

• Приемлемо, если n строго ограничено малыми величинами (сотни или меньше), либо код выполняется редко и проще поддерживать наивную реализацию.
• Неприемлемо, когда n может расти до тысяч и больше или когда операция выполняется часто (внутри цикла запросов/обработчика). В таких случаях квадратичная сложность быстро становится узким местом.

Практические шаги по улучшению

1. Переосмыслите задачу — часто можно заменить двойной перебор на предобработку (хеш-таблица, индексирование, сортировка) и получить O(n) или O(n log n).
2. Оптимизируйте константы — минимизируйте вызовы методов в внутреннем цикле, используйте прямой доступ к элементам, уменьшите накладные проверки.
3. Ранний выход — для некоторых алгоритмов (как пузырёк) вставка проверки «если не было обменов → выйти» уменьшает лучший случай до O(n).
4. Выбор альтернативы — для сортировки замените пузырёк на QuickSort/MergeSort/Timsort (O(n log n)).

Квадратичная сложность. Итог

• Если видите вложенные циклы по n — загорается «красный флаг»: потенциально O(n²).
• Формула количества сравнений в пузырьке — n(n-1)/2; для n=100 это 4950, для n=1000 — 499500.
• O(n²) быстро становится непрактичной при росте входа; всегда соотносите алгоритмическую кривую с реальными n и требованиями к задержке.
• Прежде чем оптимизировать константы, подумайте о смене алгоритма — часто это даёт куда большую выгоду, чем микрооптимизации.

---

Экспоненциальная сложность — O(2^n)

Экспоненциальная сложность — одна из самых «болезненных» для практики: время выполнения растёт вдвое с добавлением каждого нового элемента. Такие алгоритмы встречаются в задачах перебора всех комбинаций/подмножеств, в наивных решениях задач комбинаторики и во многих NP-трудных задачах.

Приведённый ниже пример демонстрирует работу полного перебора всех подмножеств множества из n элементов:

метод Скрипт()
    ЭкспоненциальнаяСложность()
;

метод ЭкспоненциальнаяСложность()
    для РазмерМассива = 5 по 20 шаг 5
        Консоль.Записать("Элементов: $РазмерМассива, вызовов: ${ПодсчётПодмножеств(РазмерМассива)}")
    ;
;

метод Перебор(индекс: Число, всего: Число, Счётчик: Массив<Число>)
    Счётчик[0] += 1
    если (индекс == всего)
        возврат
    ;

    Перебор(индекс + 1, всего, Счётчик) // без текущего элемента
    Перебор(индекс + 1, всего, Счётчик) // с текущим элементом
;

метод ПодсчётПодмножеств(РазмерМассива: Число): Число
    пер Счётчик = [0]
    Перебор(0, РазмерМассива, Счётчик)
    возврат Счётчик[0]
;

Результат:

Элементов: 5, вызовов: 63  
Элементов: 10, вызовов: 2 047  
Элементов: 15, вызовов: 65 535  
Элементов: 20, вызовов: 2 097 151

Что делает этот код и почему рост — экспоненциальный

• Метод Перебор на каждом уровне делает 2 вызова: «не брать текущий элемент» и «взять текущий элемент». Это — классическое двоичное разветвление: дерево рекурсивных вызовов — полное бинарное дерево глубины n (где n = РазмерМассива).

• Счётчик инкрементируется на каждом посещённом узле (включая листья). В полном двоичном дереве с глубиной n (рассчитывая уровни от 0 до n) общее число узлов равно

  $2^{n+1} - 1.$
  Это и даёт числа: для n = 5 → $(2^{6}-1 = 63)$, для n = 10 → $(2^{11}-1 = 2047)$ и т. д.

• Заметьте: количество подмножеств равно (2^n) (это число листьев), но количество вызовов функции — немного больше, потому что в дереве есть внутренние узлы: всего

Характер роста — «каждый новый элемент удваивает объём работы»

Ключевое свойство экспоненциальной сложности: если вы добавите один элемент, число вызовов примерно удвоится. Это делает алгоритмы экспоненциального класса быстро непрактичными:

• n = 20 → вызовов ≈ 2 097 151 (≈ 2·10⁶). При очень быстрых операциях это может быть выполнимо за секунды.
• n = 25 → вызовов ≈ 67 108 863 (≈ 67·10⁶). Уже чувствительно.
• n = 30 → вызовов ≈ 2 147 483 647 (≈ 2,15·10⁹). На миллиарды операций уйдут минуты–часы, в зависимости от стоимости одной итерации.
• n = 50 → вызовов ≈ 2 251 799 813 685 247 (≈ 2,25·10¹⁵) — там уже речь о годах работы.

Чтобы дать интуитивное представление: если одна рекурсивная «штука» занимает 1 микроcекунду, то n=20 ≈ 2 с, n=30 ≈ 2 147 с (~36 мин), n=50 ≈ 2,25·10⁹ с (~71 год). Даже при 100 нс на вызов n=50 даёт многие годы.

Где такие алгоритмы появляются на практике

• Перебор всех подмножеств / размещений / перестановок (комбинаторика).
• Наивная рекурсивная реализация задач вроде подсчёта всех разбиений, всех маршрутов в полном графе

Практические последствия и рекомендации инженеру

1. Распознавание. Если в коде есть рекурсия, делающая более одного «полного» рекурсивного вызова на элемент (или циклические двойные вложения по комбинациям), это красный флаг экспоненциального роста.
2. Оценка применимости. Экспоненциальный алгоритм может быть приемлем для малых n (например, n ≤ 20–25), но быстро становится непригодным. Всегда сопоставляйте n в вашем приложении с реальным временем выполнения.
3. Архитектурные решения. Если задача критична и n потенциально велико, подумайте о других подходах: предварительная фильтрация, индексирование, разделение задачи, распределённая обработка, сокращение пространства поиска.

Экспоненциальная сложность. Вывод

Экспоненциальная сложность — это красная зона алгоритмической эффективности.
Каждое добавление нового элемента почти удваивает объём вычислений, и даже при малых входных данных время быстро выходит за разумные пределы.

Такие алгоритмы допустимы только для очень небольших n или в задачах, где других решений нет (например, при полном переборе комбинаций).
Главное — распознавать экспоненциальный рост и не допускать его в код реальных проектов без строгих ограничений по входным данным.
Разработчик не боится экспоненты — он понимает, когда её можно себе позволить, а когда нужно искать иной путь.

---

Факториальная сложность — O(n!)

Факториальная сложность — это крайняя точка роста вычислительных затрат: количество операций (и часто — объём памяти) растёт как факториал от размера входа. На практике это означает, что каждое увеличение n на единицу умножает количество возможных вариантов на n — и потому даже при небольших n перебор становится быстро невыполнимым. Приведённый ниже пример демонстрирует генерацию всех перестановок элементов массива:

метод Скрипт()
    ФакториальнаяСложность()
;

метод ФакториальнаяСложность()
    для РазмерМассива = 2 по 8 шаг 2
        знч ИсходныйМассив = ПолучитьМассивСлучайныхЧисел(РазмерМассива)
        знч МассивРезультаты = Перестановки(ИсходныйМассив)
        Консоль.Записать("Количество перестановок: ${МассивРезультаты.Размер()}")
    ;
;



// Метод перебора перестановок
метод ПереборПерестановок(ТекущаяРасстановка: Массив<Число>, Оставшиеся: Массив<Число>, Результат: Массив<Строка>) 
    если Оставшиеся.Пусто() 
        // Преобразуем текущую перестановку в строку через запятую и добавляем в результат
        Результат.Добавить(ТекущаяРасстановка.Представление())
        возврат
    ;

    для Индекс = 0 по Оставшиеся.Размер() - 1 
        знч Элемент = Оставшиеся[Индекс]

        // Создаём новую текущую перестановку
        знч НоваяТекущая = <Число>[]
        НоваяТекущая.ДобавитьВсе(ТекущаяРасстановка)
        НоваяТекущая.Добавить(Элемент)

        // Создаём массив оставшихся без текущего элемента
        знч НовыеОставшиеся = <Число>[]
        для i = 0 по Оставшиеся.Размер() - 1
            если i != Индекс 
                НовыеОставшиеся.Добавить(Оставшиеся[i])
            ;
        ;

        // Рекурсивный вызов
        ПереборПерестановок(НоваяТекущая, НовыеОставшиеся, Результат)
    ;
;

// Метод генерации всех перестановок
метод Перестановки(ИсходныйМассив: Массив<Число>): Массив<Строка> 
    знч Результат = <Строка>[]
    ПереборПерестановок(новый Массив<Число>(), ИсходныйМассив, Результат)
    возврат Результат
;

Результат:

Количество перестановок: 2
Количество перестановок: 24
Количество перестановок: 720
Количество перестановок: 40 320

Что здесь происходит и почему n!

Алгоритм генерирует все перестановки входного массива. На каждом уровне рекурсии выбирается один из оставшихся элементов для следующей позиции, после чего остаётся задача той же природы, но с на один элемент меньшим набором. Таких полных упорядоченных размещений ровно n! — факториал n:

• n! = 1 × 2 × 3 × … × n.

Для примеров выше это даёт:

• 2! = 2,
• 4! = 24,
• 6! = 720,
• 8! = 40 320.

Именно эти числа отображены в вывода программы.

Анализ сложности (временная и пространственная)

• Временная сложность: при генерации всех перестановок очевидно требуется хотя бы Θ(n!) шагов — ведь нужно посетить n! различных объектов. На практике алгоритм, который на каждой «листе» выполняет дополнительные O(n) операций (например, копирование префикса, конкатенация, формирование строки), имеет временную сложность Θ(n · n!). Даже если генерировать перестановки «в потоке» (без копирования и без формирования строк), количество итераций остаётся пропорциональным n!.

• Память:

  • Если все перестановки сохраняются (как в примере — МассивРезультаты), то объём памяти будет Θ(n · n!) (каждая перестановка занимает O(n) места).
  • Если же перестановки обрабатываются по мере генерации и не сохраняются, а используется только стек рекурсии, дополнительная память можно сократить до O(n) (глубина рекурсии). Но это не меняет экспоненциальной временной сложности.

Как быстро «растёт» факториал — примерные масштабы

Факториал очень быстро выходит за рамки практического времени и памяти. Для наглядности:

• 10! = 3 628 800 — перебор всех перестановок может быть реализуем за секунды–минуты при очень высокой скорости обработки на современной машине;
• 12! = 479 001 600 — уже сотни миллионов вариантов: минуты–часы;
• 15! = 1 307 674 368 000 — порядка триллиона вариантов: дни–недели при 1 µs на перестановку;
• 20! ≈ 2.4329·10^18 — число вариантов настолько велико, что даже теоретические вычисления уходят в годы/века.

Даже если затраты на одну перестановку малы, факториал «съедает» любую оптимизацию констант.

Когда встречается O(n!) и как с этим работать

Алгоритмы со сложностью O(n!) появляются, когда нужно перебрать все возможные порядки или комбинации элементов. Например:

• найти все способы расставить элементы (все перестановки);
• решить задачу «в лоб», проверяя каждый возможный вариант (например, в задаче коммивояжёра — перебрать все маршруты, чтобы выбрать самый короткий);
• сгенерировать все возможные структуры или порядки (например, все топологии, расписания и т.п.).

Факториальная сложность. Вывод

Генерация всех перестановок — естественная и иногда необходимая операция, но асимптотически это O(n!), а фактические затраты часто оцениваются как Θ(n · n!) при создании/сохранении каждой перестановки. Факториал растёт невероятно быстро: то, что выполнимо для n = 8, становится невозможным для n = 15 и практически немыслимо для n = 20.

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

Заключение

Анализ сложности алгоритмов — это не абстрактная теория, а инструмент практического мышления разработчика. Он позволяет видеть не просто, как работает код сейчас, но и как он будет вести себя в будущем, когда объём данных или нагрузка системы увеличатся.

Понимание временной и пространственной сложности (O(n), O(n log n), O(n²) и других классов) даёт возможность предсказывать потенциальные узкие места ещё до появления первых проблем. Это особенно важно в системах, где масштабируемость и производительность критичны: от веб-приложений до алгоритмов машинного обучения и планирования маршрутов.

Хороший инженер не просто избегает сложных алгоритмов, а умеет оценить компромиссы между скоростью, использованием памяти и простотой реализации. Иногда линейный алгоритм уступает в скорости, но экономит память; иногда эвристика или приближённый метод оказывается более разумным выбором, чем точное решение NP-трудной задачи.

Асимптотический анализ — это язык, на котором эти компромиссы выражаются формально и объективно. Он помогает:

• сравнивать алгоритмы независимо от конкретной машины или реализации;

• выбирать решения, которые остаются эффективными при росте данных;

• строить архитектуры и системы с предсказуемой производительностью.

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