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

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
O(g(n)) ограничивает рост выбранной стоимости сверху постоянным множителем при достаточно больших n. Это не обещание секунд и не обязательно точная оценка порядка. Нужно указать размер входа, модель операций и рассматриваемый случай.
Что остаётся после удаления констант
Пусть алгоритм выполняет 3n+5 простых действий над n элементами. При росте n линейная часть определяет масштаб, а постоянная добавка перестаёт быть главной. Стоимость имеет верхнюю границу O(n). Это не означает ровно n действий: при n = 100 их 305. Обозначение описывает рост, а не точный счёт конкретной программы.
Строго говоря, линейная функция также имеет верхнюю границу O(n²), но такая граница менее точна. Для совпадающего сверху и снизу порядка используют Θ. В практической речи часто называют O(n) «линейной сложностью», подразумевая подходящую тесную оценку. В учебном решении полезно различать формальный верхний предел и точный порядок, чтобы не делать лишних выводов из одной буквы O.
Почему меньшее O не гарантирует победу на каждом входе
Алгоритм А требует 1000n условных действий, Б — n². При n = 10 первый делает 10000, второй 100; при n = 10000 первый 10000000, второй 100000000. Константа важна на небольшом диапазоне, но квадратичный рост в итоге становится дороже. Сравнение не переводится в секунды без стоимости конкретных операций и среды.
Даже одна операция над целым числом может стоить по-разному при разной длине его записи. Модель с постоянной ценой арифметики подходит не всем задачам о больших числах. Кроме того, чтение диска, сеть и кеш могут менять фактическое время. Асимптотика помогает оценить масштабируемость, а измерение — поведение реализации в заданных условиях; они дополняют друг друга.
Пример
Стоимость f(n) = 7n²+2n+9. Какая обычная тесная оценка порядка роста?
Квадратичная: Θ(n²), следовательно и O(n²). Старший член определяет рост при больших n, но точное число действий не равно n².
Как назвать случай и не скрыть работу
Линейный поиск может найти элемент первым сравнением, а при отсутствии пройти весь список. Лучший случай имеет постоянную стоимость, худший — линейную. Средняя оценка требует модели распределения входов. Нельзя сообщать лучший случай как обещание любого запроса или средний случай без вероятностных предположений.
Размер n тоже нужно определить: число строк, символов, вершин или битов — разные параметры. Функция может быть линейной по длине записи числа и экспоненциальной по другому выбранному параметру. При проверке кода учитывают скрытые циклы в сортировке, поиске и копировании, а не только число строк программы. Короткая запись не является доказательством малой стоимости.
От чтения к действию
А теперь — вы
Частые вопросы
O(n) означает ровно n миллисекунд?
Нет. Это асимптотическая граница выбранной стоимости, а не единица времени.
Линейная функция может быть O(n²)?
Формально да, как более грубая верхняя граница. Для точного порядка полезно обозначение Θ.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как посчитать число действий вложенных циклов с зависимой границей
Считаем действия вложенных циклов с зависимой границей, выводим треугольную сумму и отличаем фактическое число итераций от числа уровней вложенности.
Открыть темуПочему индекс ускоряет поиск ценой места и обновлений
Выбираем индекс для конкретного запроса, отличаем индексный поиск от полного просмотра и проверяем цену хранения и обновления вместо обещания ускорить любой SELECT.
Открыть тему