我在理解对数（Lcc）和统一（Ucc）成本标准之间的区别以及如何在计算中使用它时遇到了一些问题。
有人可以解释一下两者之间的区别，或许可以说明如何计算 A+B*C 等问题的复杂性
（是的，这是作业的一部分 =））
感谢您的帮助！
/马丁
问问题
3718 次
4 回答
8
统一成本标准为每个机器操作分配一个恒定的成本，而不管所涉及的位数如何，而对数成本标准为每个机器操作分配一个与所涉及的位数成比例的成本
于 2012-02-01T16:58:25.713 回答
3
问题大小影响复杂度 由于复杂度取决于问题的大小，我们将复杂度定义为问题大小的函数 定义：令 T(n) 表示应用于大小为 n 的问题的算法的复杂度。问题实例 (I) 的大小 (n) 是用于表示实例的（二进制）位数。所以问题大小是实例的二进制描述的长度。这称为对数成本标准
单位成本标准 如果您假设： - 每条计算机指令占用一个时间单位， - 每个寄存器都是一个存储单元 - 并且一个数字总是适合一个寄存器，那么您可以使用输入的数量作为问题大小，因为输入的长度（以位为单位）将是输入数量的常数倍。
于 2011-11-08T16:21:07.120 回答
2
统一成本标准假设每条指令占用一个时间单位，并且每个寄存器都需要一个空间单位。
对数成本标准假设每条指令占用对数个时间单位（相对于操作数的长度），并且每个寄存器都需要对数个空间单位。
简单来说，这意味着统一成本标准计算操作的数量，而对数成本标准计算位操作的数量。
例如，假设我们有一个 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 次加法计算需要一个单位时间。
在空间方面也可以进行类似的分析。寄存器要么占用恒定数量的空间（在统一成本标准下），要么占用对数数量的空间（在统一成本标准下）。
于 2016-03-15T21:23:52.837 回答
-2
我认为您应该对 Big O 表示法进行一些研究... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
如果有部分描述你觉得很难编辑你的问题。
于 2010-05-21T16:17:43.140 回答