Теорема. Как при равномерном, так и логарифмическом весе команд для любой РАМ-(РАМ*-)программы с временной сложностью T(n) существует такая постоянная R, что найдется эквивалентная РАМ*-(РАМ-)программа, временная сложность которой не превосходит RT(n).
РАМ и РАМ* - более сложные модели вычислений, чем это часто бывает необходимо. Поэтому используется ряд других моделей, которые наследуют одни черты РАМ и игнорируют другие: неветвящиеся программы, битовые вычисления, операции с двоичными векторами, деревья решений. Простейшая модель вычислений - машина Тьюринга.
Определение. Говорят, что неотрицательные функции f1(n) и f2(n) полиномиально связаны (эквивалентны), если найдутся такие полиномы P1(x) и P2(x), что для всех n справедливо неравенство f1(n)P1(f2(n)) и f2(n)P2(f1(n)).
Пример 2.1. Пусть f1(n)=2n2 и f2=n5.Покажем, что функции f1 и f2 полиномиально связаны, для чего введем в рассмотрение полиномы P1(x)=2x и p2(x)=x3. Имеем 2n22(n5) и n5(2n2)3=8n6.
Пример 2.2. Для функций f1(n)=n2 и f2(n)=2n не удается подобрать такие полиномы P1(x) и P2(x) , выполнились чтобы неравенства f1(n)P1(f2(n)) и f2(n)P2(f1(n)) при любом n ,так как показательная функция с ростом n растет быстрее степенной.
Do'stlaringiz bilan baham: |