У меня возникла проблема, чтобы понять разницу между логарифмическими (Lcc) и едиными (Ucc) критериями стоимости, а также как использовать их в расчетах.
Может кто-нибудь объяснить разницу между ними и, возможно, показать, как рассчитать сложность для такой проблемы, как A + B * C
(Да, это часть задания =))
Спасибо за любую помощь!
/Мартин
Единые критерии стоимости присваивают каждой машинной операции постоянную стоимость независимо от количества задействованных битов, В то время как логарифмические критерии стоимости присваивают каждой машинной операции стоимость, пропорциональную количеству задействованных битов.
Размер задачи влияет на сложность Поскольку сложность зависит от размера проблемы, мы определяем сложность как функцию размера задачи. Определение: Пусть T(n) обозначает сложность алгоритма, применяемого к задаче размера n. Размер (n) экземпляра задачи (I) — это количество (двоичных) битов, используемых для представления экземпляра. Таким образом, размер проблемы — это длина бинарного описания экземпляра. Это называется логарифмическим критерием стоимости.
Критерий удельной стоимости Если вы предполагаете, что: - каждая компьютерная инструкция занимает одну единицу времени, - каждый регистр является одной единицей хранения - и что число всегда помещается в регистре, то вы можете использовать количество входных данных в качестве размера задачи, поскольку длина входных данных (в битах) будет постоянным, умноженным на количество входов.
Единые критерии стоимости предполагают, что каждая инструкция занимает одну единицу времени и что каждому регистру требуется одна единица пространства.
Критерии логарифмической стоимости предполагают, что каждая инструкция занимает логарифмическое количество единиц времени (относительно длины операндов) и что каждому регистру требуется логарифмическое количество единиц пространства.
Проще говоря, это означает, что единые критерии стоимости подсчитывают количество операций, а логарифмические критерии стоимости подсчитывают количество битовых операций.
Например, предположим, что у нас есть 8-битный сумматор.
Если мы используем единые критерии стоимости для анализа времени работы сумматора, мы бы сказали, что добавление занимает одну единицу времени; т. е. T(N)=1.
Если мы используем логарифмический критерий стоимости для анализа времени работы сумматора, мы бы сказали, что сложение занимает lgn единиц времени; т. е. T(N)=lgn, где n — число для наихудшего случая, которое вам придется добавить с точки зрения временной сложности (в этом примере n будет равно 256). Таким образом, Т(N)=8.
Более конкретно, скажем, мы добавляем 256 к 32. Чтобы выполнить сложение, мы должны сложить двоичные биты вместе в столбце 1s, столбце 2s, столбце 4s и т. д. (столбцы означают расположение битов). Число 256 требует 8 бит. Здесь в нашем анализе появляются логарифмы. lg256=8. Таким образом, чтобы сложить два числа, мы должны выполнить сложение по 8 столбцам. Логарифмические критерии стоимости говорят о том, что каждый из этих 8 дополнительных расчетов занимает одну единицу времени. Единые критерии стоимости говорят о том, что весь набор из 8 дополнительных расчетов занимает одну единицу времени.
Подобный анализ может быть сделан и с точки зрения пространства. Регистры занимают либо постоянное количество места (при единых критериях стоимости), либо логарифмическое количество места (при единых критериях стоимости).
Я думаю, вам следует немного изучить нотацию Big O... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
Если есть часть описания, которую вы считаете трудной, отредактируйте свой вопрос.
