algorithm - 多项式时间复杂度

Question

有这段代码来自 here

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

要进行此计算，您需要一些基本的原始系统。例如在 The art of Computer programming 中，Knuth 使用 MIX 计算机来进行此类计算。对于这种计算，不同的基础计算机可能有不同的指令和不同的结果。在您的特定示例中，一种常见的设置方法是:

• 散列 <- len (1 op)
• 我 <- 0(1 次操作)
• i < len, i++ (2*n ops)
• key[i] 查找(n 操作)
• hash + key[i] (n ops)
• 哈希 <- 哈希 + 键(n 操作)
• hash % prime (1 op)

这将加起来为 5n + 3。

变化可能是这样的:

• 声明/创建两个 hash 和 i 可能很耗时。由于声明，普通 cpu 可能不需要做额外的工作，想想寄存器/堆栈存储。
• hash += hash + key[i] 可能被算作基本系统上的一个操作，依此类推。

编辑:请注意，这类计算主要用作假设硬件上的思想实验。除非在极少数情况下，否则现实生活中的处理器很可能不会完全按照这些计算运行。