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

Пусть даны две программы, время выполнения одной 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²

Анализ программы на псевдоязыке

Реализация программы трудоемкости отличается от трудоемкости на псевдоязыке, как в большую, так и в меньшую сторону, если существует Яну (Яву), использующие аппаратные особенности процессора, что уменьшает трудоемкость выполнения программ; в тоже время на псевдоязыке могут использоваться операторы, при анализе трудоемкость принимается U(1), тогда как реализация на языке программирования будет зависеть от длины входа, т.е. от n. Поэтому при анализе программы на псевдокоде алгоритм необходимо детализировать до такого уровня, который слабо бы зависел от реализации программиста.

Вообще необходимо оговаривать все циклические процессы в алгоритмах в том числе и рекурсии, так как каждый цикл увеличивает показатель функции роста на единицу, подсчитав количество циклов можно оценить максимальный показатель многочленов.

Абстрактный тип данных в списках

С математической точки зрения линейный список - это множество, состоящее из n>0 элементов или узлов X1,X2,Xn, структурные свойства которого (множества) по сути, ограничиваются лишь линейно (в математическом смысле), т.е. относительным порядком следования положения узлов, определяемыми условиями, что если n>0, X1 первый элемент последовательности.

1<k<n1, если k измениться, тогда Xk предследствует элемент Xk-1.