Информатика · объяснение и практика

Что сравнивает порядок роста алгоритма без обещания секунд

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

Главная мысль

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 тоже нужно определить: число строк, символов, вершин или битов — разные параметры. Функция может быть линейной по длине записи числа и экспоненциальной по другому выбранному параметру. При проверке кода учитывают скрытые циклы в сортировке, поиске и копировании, а не только число строк программы. Короткая запись не является доказательством малой стоимости.

От чтения к действию

А теперь — вы

Алгоритм всегда делает 5n+10 сравнений. Каков его тесный порядок по n?

Частые вопросы

O(n) означает ровно n миллисекунд?

Нет. Это асимптотическая граница выбранной стоимости, а не единица времени.

Линейная функция может быть O(n²)?

Формально да, как более грубая верхняя граница. Для точного порядка полезно обозначение Θ.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться