Рост по «О большое»: во что на самом деле обходится каждый класс сложности

Ваши данные

Два алгоритма лицом к лицу

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

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

Результаты

Где один обгоняет другого, в элементах—
Число операций у каждого при размере выше—

С числами, с которых начинается страница, точка пересечения — 439 элементов. Тот, кто берётся за «лучший» класс на списке из двухсот, сделал программу медленнее, а код труднее, и нотация не предупредила: она о том, что происходит в конце концов, а не о том, что происходит с вами.

Каждый класс при этом размере

КлассОперацииВремяВо сколько раз больше, если вход удвоится

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

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

Это же объясняет, почему разрыв между классами скучен на малых размерах и жесток на больших. На десяти элементах n log n и n в квадрате отличаются втрое, чего ни один пользователь не заметит. На тысяче — в сто раз, на миллионе — в пятьдесят тысяч раз. Те же два алгоритма, тот же код, изменился только вход.

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

Реакции

0

0 Комментарии

User profile image

Прокомментируйте первым

Значит ли лучший класс сложности более быструю программу?

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

С числами, с которых начинается страница, квадратичный алгоритм с лёгкой константой обыгрывает n log n с константой пятьдесят на любом входе меньше 439 элементов. Выше лучший класс уходит вперёд и лидерства больше не отдаёт.

Почему эта страница не читает мой код?

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

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

Что на самом деле происходит при удвоении входа?

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

Факториал так даже не работает. Один добавленный элемент умножает стоимость на новое число, поэтому двадцать первый элемент стоит двадцать один раз всю задачу на двадцать.

КлассВо сколько раз больше при удвоении входа, на тысяче элементов
O(n)2
O(n log n)2,2
O(n²)4
O(n³)8
O(2ⁿ)1,07 x 10^301
Почему точный коммивояжёр невозможен на двадцати городах?

Потому что двадцать факториал — это 2,4 миллиона миллионов миллионов шагов, а при миллиарде операций в секунду это семьдесят семь лет. Те же двадцать элементов при двух в степени n занимают около тысячной доли секунды.

Это и есть практическая разница между экспонентой и факториалом, и именно поэтому их стоит разделять, а не сваливать оба в «невозможно».