Ограниченность показателя функции роста

Пусть даны две программы, время выполнения одной O(n²), а вторая O(n³), причем при определенной комбинации компилятора ПК одна программа выполнятся за 100n², а вторая 5n³ может ли быть вторая программа предпочтительней другой? При n < 20, вторая функция предпочтительнее, т.к. для ее выполнения требуется меньше операций: 5n³ < 100n². Однако, при n > 20 первая программа становится предпочтительней. Вообще выбор определяется между программами на основе оценки трудоемкости и по возможности выбирается функция с полиномом меньшей степени. Чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Рассмотрим два случая использования этих алгоритмов: пусть в первом случае для решения задачи выделено машинное время T1 = 10000 мс, а во тором – в 100 раз больше (см таблицу).

Таблица

То есть, если выделено T₁ времени на ЭВМ для решения задачи этими алгоритмами, тогда мы успеем решить задачу размерности 10. Заплатив за время в 100 раз больше, и получив время в 100 раз больше, мы можем за новое время решить задачу размерности 100 и 60.

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

Увеличение времени соответствует увеличению производительности ЦП (центрального процессора) от версии к версии. Однако существуют такие задачи с такими функциями роста, производительность процессов которых слабо влияет.

Практически вычислимыми, т.е. реализуемыми за приемлемое время являются алгоритмы полиномиального класса трудоемкости – это алгоритмы для которых асимптотическая оценка функции роста трудоемкости алгоритма представляет собой полином некоторой степени O(f(n)) = n^k, где k – константа.

Рассмотрим основные классы алгоритмов на основе вида их функции роста.