对数与统一成本标准之间的区别

Question

我在理解对数（Lcc）和统一（Ucc）成本标准之间的差异以及如何在计算中使用它时遇到了一些问题。

可能有人请解释两者或许之间的差异表明如何计算的复杂性对于像A + B * C

（是的，这是一个任务的一部分=））

THX问题任何帮助！

/Marthin

Answer 1

统一成本标准分配一个恒定成本每台机器操作，而不管所涉及WHILE对数成本标准比特数的分配到每个机操作成比例的比特的数目的费用涉及

Answer 2

，我认为你应该做一些研究，大O符号... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

如果有说明书的一部分，你发现很难编辑你的问题。

Answer 3

问题大小影响复杂 由于复杂性依赖于 问题的大小，我们定义复杂成为问题大小的函数 定义：设T（n）表示的复杂性 被施加到所涉及的算法问题 大小n。 问题实例（I）的大小（n）是用于表示 实例的（二进制）位数 。所以问题的大小是实例的二进制描述的长度 。 这就是所谓的对数费用标准

单位成本的标准 如果假设： - 每一台计算机指令需要一个时间 单位， - 每个寄存器是一个存储单元 - 而且一些总是在寄存器适合 然后你可以使用输入的数量作为 问题的大小，因为输入的长度（以位为单位） 将是一个常数倍的输入。

Answer 4

统一成本标准假设每条指令都需要一个单位时间，并且每个寄存器都需要一个单位的空间。

对数成本标准假设每条指令都采用对数数量的时间单位（相对于操作数的长度），并且每个寄存器都需要对数个单位的空间。

简而言之，这意味着统一成本标准计算操作次数，而对数成本标准计算位操作次数。

例如，假设我们有一个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个加法计算需要一个单位时间。

也可以根据空间进行相似分析。登记册要么占用一定数量的空间（在统一的成本标准下），要么占用对数的空间（在统一的成本标准下）。