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