代码之家  ›  专栏  ›  技术社区  ›  Adrian Munteanu

除以2和上限,直到剩余1

  •  1
  • Adrian Munteanu  · 技术社区  · 11 年前

    仅对自然数具有以下算法: rounds(n)={1,如果n=1;1+个rounds,则为ceil(n/2),否则为} 所以用编程语言写作

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

    我认为这具有时间复杂性O(logn)

    有更好的复杂性吗?

    2 回复  |  直到 11 年前
        1
  •  1
  •   Daniel Fischer    11 年前

    首先列出从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
    

    那么,当 细胞免疫球蛋白(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为底的对数。如果没有,您可以使用获得比递归更快的版本 one of the classic 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秒 rounds 对于1到100000000,比特破解

    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秒。

    如果不使用固定宽度的类型,而是使用任意精度的整数,情况会有所改变。naive循环(或递归)仍然使用 Θ(log n) 步骤,但步骤需要 (日志n) 平均时间(或更糟),所以总的来说,你有 Θ(log² n) 算法(或更糟)。然后使用上面的公式不仅可以提供具有较低常数因子的实现,而且可以提供具有更低算法复杂度的实现。

    • 对于合适的表示,可以在恒定时间内进行与1的比较, O(log n) 是合理陈述的最坏情况。
    • 从正整数中减去1 O(日志n) 以获得合理陈述。
    • 对于某些表示,可以在恒定时间内计算以2为底的对数 O(日志n) 对于其他合理的表示[如果它们使用2次幂的基数,我半熟悉的所有任意精度库都是这样做的;如果它们使用10次幂的碱基,那就不同了]。
        2
  •  1
  •   Falk Hüffner    11 年前

    如果你认为算法是迭代的,数字是二进制的,那么这个函数会移出最低位,如果移出的是1,则会将数字增加1。因此,除了增量之外,它对数字中的位数(即最高的1的位置)进行计数。增量最终会使结果增加一,除非数字的形式是1000……因此,您可以得到位数加一,或者如果数字是二的幂,则可以得到位数。根据您的机器型号,这可能比O(logn)计算得更快。