对数成本标准和统一成本标准之间的差异
我在理解对数（Lcc）和统一（Ucc）成本标准之间的差异以及如何在计算中使用它时遇到一些问题。
有人可以解释一下两者之间的区别，也许可以展示如何计算像 A+B*C 这样的问题的复杂性
（是的，这是作业的一部分=））
谢谢您的帮助！
/马丁
I'v got some problem to understand the difference between Logarithmic(Lcc) and Uniform(Ucc) cost criteria and also how to use it in calculations.
Could someone please explain the difference between the two and perhaps show how to calculate the complexity for a problem like A+B*C
(Yes this is part of an assignment =) )
Thx for any help!
/Marthin
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
统一成本标准为每个机器操作分配恒定的成本，无论涉及的位数如何，而对数成本标准为每个机器操作分配与涉及的位数成比例的成本
Uniform Cost Criteria assigns a constant cost to every machine operation regardless of the number of bits involved WHILE Logarithm Cost Criteria assigns a cost to every machine operation proportional to the number of bits involved
问题大小影响复杂性
由于复杂性取决于数据的大小
问题我们将复杂性定义为一个函数
问题大小
定义：设 T(n) 表示复杂度
应用于以下问题的算法
尺寸
问题实例 (I) 的大小 (n) 是
用于表示的（二进制）位数
实例。所以问题的大小就是问题的长度
实例的二进制描述。
这称为对数成本标准
单位成本标准
如果您假设：
- 每条计算机指令都需要一次
单元，
- 每个寄存器都是一个存储单元
- 并且一个数字总是适合寄存器
那么你可以使用输入的数量
自输入长度（以位为单位）以来的问题大小
将是常数乘以输入数量。
Problem size influence complexity
Since complexity depends on the size of the
problem we define complexity to be a function
of problem size
Definition: Let T(n) denote the complexity for
an algorithm that is applied to a problem of
size n.
The size (n) of a problem instance (I) is the
number of (binary) bits used to represent the
instance. So problem size is the length of the
binary description of the instance.
This is called Logarithmic cost criteria
Unit Cost Criteria
If you assume that:
- every computer instruction takes one time
unit,
- every register is one storage unit
- and that a number always fits in a register
then you can use the number of inputs as
problem size since the length of input (in bits)
will be a constant times the number of inputs.
统一成本标准假设每条指令需要一个时间单位，并且每个寄存器需要一个空间单位。
对数成本标准假设每条指令需要对数个时间单位（相对于操作数的长度），并且每个寄存器需要对数个空间单位。
简单来说，这意味着统一成本标准计算操作的数量，对数成本标准计算位操作的数量。
例如，假设我们有一个 8 位加法器。
如果我们使用统一的成本标准来分析加法器的运行时间，我们会说加法需要一个时间单位；即T(N)=1。
如果我们使用对数成本标准来分析加法器的运行时间，我们会说加法需要 lgn 时间单位；即，T(N)=lgn，其中 n 是您必须根据时间复杂度添加的最坏情况数字（在本例中，n 为 256）。因此，T(N)=8。
更具体地说，假设我们要将 256 与 32 相加。要执行加法，我们必须将 1s 列、2s 列、4s 列等（这些列表示位位置）中的二进制位相加。数字 256 需要 8 位。这就是对数进入我们分析的地方。 LG256=8。因此，要将两个数字相加，我们必须对 8 列进行加法。对数成本标准表明，这 8 次加法计算中的每一次都需要一个时间单位。统一成本标准规定，整套 8 次加法计算需要一个时间单位。
在空间方面也可以进行类似的分析。寄存器要么占用恒定量的空间（在统一成本标准下），要么占用对数空间量（在统一成本标准下）。
Uniform cost criteria assume that every instruction takes a single unit of time and that every register requires a single unit of space.
Logarithmic cost criteria assume that every instruction takes a logarithmic number of time units (with respect to the length of the operands) and that every register requires a logarithmic number of units of space.
In simpler terms, what this means is that uniform cost criteria count the number of operations, and logarithmic cost criteria count the number of bit operations.
For example, suppose we have an 8-bit adder.
If we're using uniform cost criteria to analyze the run-time of the adder, we would say that addition takes a single time unit; i.e., T(N)=1.
If we're using logarithmic cost criteria to analyze the run-time of the adder, we would say that addition takes lgn time units; i.e., T(N)=lgn, where n is the worst case number you would have to add in terms of time complexity (in this example, n would be 256). Thus, T(N)=8.
More specifically, say we're adding 256 to 32. To perform the addition, we have to add the binary bits together in the 1s column, the 2s column, the 4s column, etc (columns meaning the bit locations). The number 256 requires 8 bits. This is where logarithms come into our analysis. lg256=8. So to add the two numbers, we have to perform addition on 8 columns. Logarithmic cost criteria say that each of these 8 addition calculations takes a single unit of time. Uniform cost criteria say that the entire set of 8 addition calculations takes a single unit of time.
Similar analysis can be made in terms of space as well. Registers either take up a constant amount of space (under uniform cost criteria) or a logarithmic amount of space (under uniform cost criteria).
我认为你应该对 Big O 表示法做一些研究...http://en.wikipedia。 org/wiki/Big_O_notation#Orders_of_common_functions
如果您发现描述的一部分很难编辑您的问题。
I think you should do some research on Big O notation... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
If there is a part of the description you find difficult edit your question.