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

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

f(n) T1 = 10000 мс T2 = 100*10000 затрат в 100 раз выше

100n² 10 n2 = 100 рост размерности задачи в 10 раз

5n³ 12 n2 = 60 в 5 раз

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

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

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

Практически вычислимыми, т.е. реализуемыми являются алгоритмы f(n) = n(k - степень), где k константа, полиномиальный класс. Линейные алгоритмы вид C*n, между которыми находятся задачи C*n и C*n², где n – логарифм время сортировки, C*n< n*log 2n < C*n²