1

仅对自然数具有以下算法：rounds(n)={1, if n=1; 1+rounds(ceil(n/2)), else} 所以用编程语言编写这将是

int rounds(int n){
    if(n==1)
        return 1;
    return 1+rounds(ceil(n/2));
}

我认为这具有时间复杂度 O(log n)

有更好的复杂性吗？

4

2 回答 2

1

如果您认为算法是迭代的，而数字是二进制的，那么这个函数会移出最低位，如果移出的是 1，则将数字加 1。因此，除了增量之外，它计算数字中的位数（即最高1的位置）。增量最终会将结果加一，除非数字的形式为 1000...。因此，您将获得位数加一，或者如果数字是 2 的幂，则获得位数。根据您的机器型号，这可能比 O(log n) 计算得更快。

于 2013-02-27T13:57:09.777 回答
1

首先列出从 1 开始的结果，

rounds(1) = 1
rounds(2) = 1 + rounds(2/2) = 1 + 1 = 2

接下来，当ceil(n/2)是 2 时，rounds(n)将是 3。那是n = 3和n = 4。

rounds(3) = rounds(4) = 3

那么，当ceil(n/2)是 3 或 4 时，结果将是 4。3 <= ceil(n/2) <= 4当且仅当 时发生2*3-1 <= n <= 2*4，所以

round(5) = ... = rounds(8) = 4

继续，你可以看到

rounds(n) = k+2 if 2^k < n <= 2^(k+1)

通过感应。

您可以将其重写为

rounds(n) = 2 + floor(log_2(n-1)) if n > 1 [and rounds(1) = 1]

并且在数学上，您还可以n = 1通过将其重写为

rounds(n) = 1 + floor(log_2(2*n-1))

但是，如果您使用固定宽度类型，最后一个公式可能会溢出。

所以问题是

  • 你能多快将一个数字与 1 进行比较，
  • 你能多快从一个数中减去 1，
  • 你能以多快的速度计算正整数的以 2 为底的对数的（下限）？

对于固定宽度类型，即有界范围，所有这些当然都是 O(1) 操作，但是您可能仍然有兴趣使其尽可能高效，即使计算复杂度没有进入游戏。

对于本机机器类型 -通常是 - 比较int和long减去整数是非常快的机器指令，因此唯一可能有问题的是以 2 为底的对数。

许多处理器都有一条机器指令来计算机器类型值的前导 0 位，如果编译器可以访问它，您将获得以 2 为底的对数的非常快速的实现。如果没有，您可以获得比使用经典 bit-hacks 之一的递归更快的版本。

例如，足够新的 gcc 和 clang 版本有一个__builtin_clz（分别__builtin_clzl用于 64 位类型），bsr*如果处理器上存在该指令，则映射到该指令，并且如果没有提供，则可能是使用一些位旋转的良好实现由处理器。

版本

unsigned rounds(unsigned long n) {
    if (n <= 1) return n;
    return sizeof n * CHAR_BIT + 1 - __builtin_clzl(n-1);
}

使用该bsrq指令需要（在我的盒子上）0.165 秒来计算rounds1 到 100,000,000，bit-hack

unsigned rounds(unsigned n) {
    if (n <= 1) return n;
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n -= (n >> 1) & 0x55555555;
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    return ((n * 0x01010101) >> 24)+1;
}

耗时 0.626 秒，而天真的循环

unsigned rounds(unsigned n) {
    unsigned r = 1;
    while(n > 1) {
        ++r;
        n = (n+1)/2;
    }
    return r;
}

需要 1.865 秒。

如果您不使用固定宽度类型，而是使用任意精度整数，那么情况会发生一些变化。天真的循环（或递归）仍然使用Θ(log n)步骤，但这些步骤Θ(log n)平均需要时间（或更糟），所以总的来说你有一个Θ(log² n)算法（或更糟）。那么使用上面的公式不仅可以提供具有较低常数因子的实现，而且可以提供具有较低算法复杂度的实现。

  • 对于合适的表示，可以在恒定时间内与 1 进行比较，O(log n)这是合理表示的最坏情况。
  • 从一个正整数中减去 1 可以获得O(log n)合理的表示。
  • 对于某些表示和其他合理的表示，可以在恒定时间内完成以 2 为底的对数的（下限）计算O(log n)[如果他们使用 2 次方基数，我对所有任意精度库都很熟悉与做; 如果他们使用 10 次方基数，那将是不同的]。
于 2013-02-27T17:18:52.740 回答