Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вычислительная сложность РАМ-программ.

Таблица действий команд РАМ-машины.

_­В принципе, можно было бы к нашему набору добавить любые другие команды, встречающиеся в реальных вычислительных машинах, такие, как логические или символьные операции, и при этом, порядок сложности задач не изменится.

РАМ-программа задаёт отображение множества символов, записанное на входной ленте, во множество выходных символов, т.е.

P: RX → RY

Так как при некоторых входных данных программа Р может не останавливаться, то это отображение является частичным (т.е. для некоторых входов оно может быть не определено).

Это отображение может быть использовано для преобразования числовых и символьных данных.

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

y = f(x₁, x₂, …, x_n)

А во втором случае программа Р является распознавателем некоторого языка.

Языком, допускаемым программой Р, называется множество всех входных цепочек (слов), которые воспринимаются и обрабатываются программой.

Пример:

Какие действия выполняют команды LOAD a, если а принимает значения равны i, i и *i, а также известно, что i=5, C(5)=7, C(7)=12.

1. LOAD =i LOAD =5 C(A) ← 5

2. LOAD i LOAD 5 C(A) ← C(5) = 7

3. LOAD *i LOAD *5 C(A) ← C(C(5))=C(7) = 12

Вычислительная сложность РАМ-программ.

Эффективность алгоритмов характеризуют временная и емкостная сложности, которые рассматриваются как функции размера входа n. Мы будем рассматривать сложность в худшем случае и среднюю сложность.

Если при данном размере входа n в качестве меры сложности берётся максимальная из сложностей (по всем входам этого размера), то она называется сложностью в худшем случае.

Если в качестве меры сложности берётся "средняя" сложность по всем входам данного размера, то она называется средней (или усреднённой) сложностью.

Временная сложность в худшем случае (или просто временная сложность) РАМ-программы - это функция T(n), равная наибольшей (по всем входам размера n) из сумм времён затраченных на каждую выполненную команду.

Временная сложность в среднем - это среднее значение, взятое по всем входам размера n, тех же самых сумм.

Емкостная сложность в худшем случае РАМ-программы - это функция S(n), равная наибольшей (по всем входам размера n) из сумм емкостей всех регистров, к которым было обращение.

Емкостная сложность в среднем - это среднее значение сумм.

Чтобы точно определить временную и емкостную сложность, надо указать время, необходимое для выполнения каждой РАМ-команды, и объём памяти, используемый каждым регистром.

Рассмотрим два весовых критерия:

Ø Равномерный весовой критерий. При равномерном весовом критерии каждая РАМ-команда затрачивает одну единицу времени, и каждый регистр использует одну единицу памяти.

Ø Логарифмический весовой критерий. Он более реалистичен и учитывает ограниченность размера реальной ячейки памяти.

Пусть l(i) - логарифмическая функция на целых числах, определим её следующим образом:

,

тогда логарифмические веса t(a) для всех трёх возможных типов операнда а имеют вид:

Рассмотрим веса РАМ-команд.

Здесь учитывается, что для представления целого числа n в регистре требуется [log n] + 1 битов (бит - единица памяти). Регистры же (по нашему допущению) могут содержать произвольно большие числа.

Логарифмический весовой критерий основан на грубом допущении, что вес каждой команды (или цена выполнения команды) пропорционален длине её операндов.

Пример:

Рассмотрим вес команды ADD a, если a=*i

ADD *i C(A)← C(A) + C(C(i))

Временная сложность команды определяется следующим образом: просмотр целого числа i занимает время l(i), затем, чтобы прочитать содержимое C(i) регистра i и определить его местоположение, понадобиться время l(C(i)), наконец считывание содержимого из регистра C(i) требует время l(C(C(i))).

Так как мы все действия выполняем в сумматоре, складывая найденое число с содержимым сумматора, то для этого нужно время l(C(A)). Следовательно вес ADD *a:

l(C(A)) + l(i) + l(C(i)) + l(C(C(i)))

определим логарифмическую сложность РАМ-программы как сумму по всем работавшим регистрам, включая сумматор, величин l(i), где x_i - наибольшее по абсолютной величине целое число, содержащееся в i-ом регистре за время вычислений.

Пример:

Оценим временную и емкостную сложность РАМ-программы, вычисляющей функцию f = nⁿ.

При подсчёте временной сложности будет доминировать цикл с командой MULT, которая выполняется (n-1) раз.

Когда команда выполняется i-ый раз сумматор А содержит nⁱ, а регистр С содержит n. При равномерном весовом критерии (как мы отмкчали) на выполнение каждой команды MULT потребуется 1 единица времени, и поэтому на выполнение всех команд умножения тратится время О(n).

При логарифмическом весовом критерии i-я команда умножения занимает время

MULT a l(C(A)) + t(a)

i- MULT l(nⁱ) + l(n) ≈ [log |nⁱ|] + 1 + log n ≈ (i + 1) log n

Тогда время выполнения всех команд умножения равно:

, что составляет О(n² log n)

Емкостная сложность определяется числами, которые хранятся в регистрах от А до D. При равномерном весовом критерии емкостная сложность составляет О(1), а при логарифмическом - О(), т.к. наибольшее целое число среди содержащихся в этих регистрах есть nⁿ, а:

log (nⁿ) = [log |nⁿ|] + 1 ≈ n log n

Таким образом, сложности функции nⁿ таковы:

Рассмотрим целесообразность оценки при использовании равномерного и логарифмического веса.

Для этой программы равномерный вес реалистичен только в ситуации, когда столь большое целое, как nⁿ , записывается в виде одного машинного слова.

Если же значение nⁿ превышает одно машинное слово, то тогда даже логарифмическая временная сложность до некоторой степени нереалистична, т.к. она предполагает, что 2 целых числа i и j перемножаются за время O(l(i) + l(j)), а возможность этого неизвестна.