Главная | Обратная связь | Поможем написать вашу работу!

Входными переменными служат коэффициенты и неопределенная переменная х Выходной переменной будет значение полинома р.

По правилу Горнера для вычисления можно использовать алгоритм:

1) для n=1,

2) для п=2,

3) для =3

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

2. Битовые вычисления (схемы из функциональных элементов)

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

Все переменные принимают значения 0 или 1, т. е. это биты,

2) используются логические операции вместо арифметических (and обозначается через &, or — через . exclusive or — через , not — через — ).

Операции с двоичными векторами

Можно было бы не ограничивать значения переменных символами 0 и 1, а разрешить переменным принимать в качестве значения любой вектор из 0 и 1. Фактически двоичные векторы фиксированной длины очевидным образом соответствуют целым числам, так что здесь не допускается ничего такого, что не допускалось бы в РАМ, т. е., когда это удобно, просто разрешаются регистры неограниченного размера.

Деревья решений

Выше приведены три модификации РАМ, игнорирующие команды разветвления и учитывающие только те шаги программы, которые включают арифметический счет. В некоторых задачах удобно в качестве основной меры сложности брать число выполняемых команд разветвления. В случае сортировки, например, выходы совпадают со входами с точностью до порядка. Поэтому разумно рассматривать модель, в которой все шаги дают разветвления, возникающие в результате сравнения двух величин. Обычно программу, состоящую из разветвлений, представляют в виде двоичного дерева, называемого деревом решений. Каждый внутренний узел представляет один из шагов решения. Сравнение, представленное корнем, выполняется первым, и затем "управление" передается одному из его сыновей в зависимости от исхода теста до тех пор, пока не будет достигнут лист дерева. Нужный результат находится на достигнутом листе

Рис. 10. Дерево решений для задачи сортировки трех чисел

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒

Воспользуйтесь поиском по сайту: