Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Теорема. Как при равномерном, так и логарифмическом весе команд для любой РАМ-(РАМ*-)программы с временной сложностью T(n) существует такая постоянная R, что найдется эквивалентная РАМ*-(РАМ-)программа, временная сложность которой не превосходит RT(n).
РАМ и РАМ* - более сложные модели вычислений, чем это часто бывает необходимо. Поэтому используется ряд других моделей, которые наследуют одни черты РАМ и игнорируют другие: неветвящиеся программы, битовые вычисления, операции с двоичными векторами, деревья решений. Простейшая модель вычислений - машина Тьюринга.
Определение. Говорят, что неотрицательные функции f₁(n) и f₂(n) полиномиально связаны (эквивалентны), если найдутся такие полиномы P₁(x) и P₂(x), что для всех n справедливо неравенство f₁(n)P₁(f₂(n)) и f₂(n)P₂(f₁(n)).
Пример 2.1. Пусть f₁(n)=2n² и f₂=n⁵.Покажем, что функции f₁ и f₂ полиномиально связаны, для чего введем в рассмотрение полиномы P₁(x)=2x и p₂(x)=x³. Имеем 2n²2(n⁵) и n⁵(2n²)³=8n⁶.
Пример 2.2. Для функций f₁(n)=n² и f₂(n)=2ⁿ не удается подобрать такие полиномы P₁(x) и P₂(x) , выполнились чтобы неравенства f₁(n)P₁(f₂(n)) и f₂(n)P₂(f₁(n)) при любом n ,так как показательная функция с ростом n растет быстрее степенной.