多项式时间复杂性

Question

ub4 additive(char *key, ub4 len, ub4 prime)
{
  ub4 hash, i;
  for (hash=len, i=0; i<len; ++i) 
    hash += key[i];
  return (hash % prime);
}

他们说这需要5n+3指令。他们是如何计算的？我应该如何计算？

Answer 1

要进行此计算，您需要一些基本的基本系统。例如，在《计算机编程艺术》中，Knuth使用MIX计算机进行此类计算。不同的基础计算机可能有不同的指令，以及这种计算的不同结果。在您的特定示例中，一种常见的设置方法是：

• hash<-len(1个操作(
• i<-0(1个操作(
• i<len，i++(2*n个操作(
• 关键字[i]查找(n个操作(
• hash+key[i](n个操作(
• hash<-hash+密钥(n个操作(
• 哈希%素数(1个操作(

这将加起来为5n+3。

变化可能沿着以下路线：

• 声明/创建两个hash和i可能是耗时的。普通的cpu可能不需要因为声明而做额外的工作，比如寄存器/堆栈存储
• hash += hash + key[i]可以被计数为在基本系统上的一个操作等等

编辑：请注意，这类计算在假设硬件上的思想实验中非常有用。除了在极少数情况下，现实生活中的处理器很可能不会像这些计算那样工作。

Answer 2

在循环内部，有5个操作在每次迭代中运行：

1. 比较i<len
2. 获取索引key[i]
3. 添加hash + key[i]
4. 分配到hash
5. 增量++i

您的循环运行n次，因此5n

在循环之外，您有3个操作：

1. 将len分配到散列hash=len
2. 将0分配给i i=0
3. 执行hash % prime

因此，5n + 3。

Answer 3

让我们开始计算指令。

1. hash=len和i=0执行一次，所以我们至少有2条指令
2. hash%prime和return至少执行一次，所以这是1条或2条指令(取决于你是否将"return"算作指令……我怀疑它们不是(
3. 循环的每次迭代都需要i<lt；len，++i，key[i]，hash+key[i]和hash=hash+key[i]。因此，对于循环的len(n(次迭代，我们有5条指令被执行一次

加起来，我们得到大约2+(1或2(+(4或5(n，因此3+4n<=T(n(<=4+5n。3+5n是合理的；确切的答案取决于你如何计算单个指令。一个更详细的模型可能会将简单的赋值计算为比模运算需要更少的时间。。。