Пусть даны две программы, время выполнения одной O(n²), а вторая O(n³), причем при определенной комбинации компилятора ПК одна программа выполнятся за 100n², а вторая 5n³ может ли быть вторая программа предпочтительней другой? При n < 20, вторая функция предпочтительнее, т.к. для ее выполнения требуется меньше операций: 5n³ < 100n². Однако, при n > 20 первая программа становится предпочтительней. Вообще выбор определяется между программами на основе оценки трудоемкости и по возможности выбирается функция с полиномом меньшей степени. Чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Рассмотрим два случая использования этих алгоритмов: пусть в первом случае для решения задачи выделено машинное время T1 = 10000 мс, а во тором – в 100 раз больше (см таблицу).
Таблица
| Функция трудоемкости решения задачи, f(n) | T1 = 10000 мс | T2 = 100*10000 | затрат в 100 раз выше |
| Размерность задачи, решаемой за время T1 и T2 | |||
| n1 | n2 | ||
| 100n² | рост размерности задачи в 10 раз | ||
| 5n³ | в 5 раз |
То есть, если выделено T1 времени на ЭВМ для решения задачи этими алгоритмами, тогда мы успеем решить задачу размерности 10. Заплатив за время в 100 раз больше, и получив время в 100 раз больше, мы можем за новое время решить задачу размерности 100 и 60.
Вывод: увеличивая время выполнения на прежних ПК эффективность решаемой задачи (размерность) уменьшается и возможна ситуация, когда на увеличение размерности хотя бы на единицу потребуется времени неизмеримо много.
Увеличение времени соответствует увеличению производительности ЦП (центрального процессора) от версии к версии. Однако существуют такие задачи с такими функциями роста, производительность процессов которых слабо влияет.
Практически вычислимыми, т.е. реализуемыми за приемлемое время являются алгоритмы полиномиального класса трудоемкости – это алгоритмы для которых асимптотическая оценка функции роста трудоемкости алгоритма представляет собой полином некоторой степени O(f(n)) = nk, где k – константа.
Рассмотрим основные классы алгоритмов на основе вида их функции роста.