Разница между логарифмическим и единообразным критериями стоимости

Question

У меня возникла проблема с пониманием разницы между критериями логарифмической (Lcc) и унифицированной (Ucc) стоимости, а также с тем, как использовать ее в расчетах.

Может, кто-нибудь объяснит разницу между ними и, возможно, покажет, как рассчитать сложность для такой задачи, как A + B * C

(Да, это часть задания =))

Спасибо за любую помощь!

/ Marthin

Answer 1

Uniform Cost Criteria назначает постоянную стоимость для каждой операции машины независимо от количества задействованных битов. В то время как Logarithm Cost Criteria назначает стоимость для каждой операции машины пропорционально количеству задействованных битов

Answer 2

Размер проблемы влияет на сложность Поскольку сложность зависит от размера Проблема, которую мы определяем сложность, чтобы быть функцией проблемы размера Определение: пусть T (n) обозначает сложность для алгоритм, который применяется к проблеме размер n. Размер (n) проблемного экземпляра (I) количество (двоичных) битов, используемых для представления пример. Таким образом, размер проблемы является длина двоичное описание экземпляра. Это называется критериями логарифмической стоимости

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

Answer 3

Критерии единообразной стоимости предполагают, что каждая инструкция занимает одну единицу времени и что каждому регистру требуется единица пространства.

Критерии логарифмической стоимости предполагают, чтокаждая инструкция принимает логарифмическое количество единиц времени (по отношению к длине операндов), и что каждому регистру требуется логарифмическое количество единиц пространства.

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

Например, , предположим, что у нас есть 8-разрядный сумматор.

Если мы 'Если бы мы использовали единые критерии стоимости для анализа времени работы сумматора, мы бы сказали, что сложение занимает одну единицу времени;то есть T (N) = 1.

Если мы используем критерии логарифмической стоимости для анализа времени работы сумматора, мы бы сказали, что сложение занимает lg⁡n единиц времени;т. е. T (N) = lgn, где n - номер наихудшего случая, который вам нужно будет добавить с точки зрения сложности времени (в этом примере n будет равно 256).Таким образом, T (N) = 8.

Более конкретно, скажем, мы добавляем 256 к 32. Чтобы выполнить сложение, нам нужно сложить двоичные биты вместе в столбце 1s, столбце 2s,Столбец 4s и т. Д. (Столбцы означают расположение битов).Число 256 требует 8 бит.Здесь логарифмы входят в наш анализ.lg256 = 8.Таким образом, чтобы сложить два числа, нам нужно сложить 8 столбцов.Критерии логарифмической стоимости говорят, что каждый из этих 8 дополнительных вычислений занимает одну единицу времени.Критерии единообразной стоимости говорят о том, что весь набор из 8 дополнительных вычислений занимает одну единицу времени.

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

Answer 4

Я думаю, вы должны провести некоторое исследование по обозначению Big O ... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

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