2

这是将十进制数字转换为二进制表示的函数的伪代码。

问题是证明一个 n 位数的 Ldiv2[A] 是 O(n)。并确定算法的运行复杂度

输入是数字 X 的十进制表示，由数字数组 A[n-1]、...、

以下算法使用“长除以二”过程 Ldiv2 将十进制数除以 2。下面的二进制转换算法将十进制数字数组 A[0..n-1] 转换为位数组 B[0, ..4n-1] 如下：

Initialize B[0, ..4n-1] array of bits,
For i = 0 to 4n-1 do:
    Begin
    B[i]= A[0] %2;   // % is the mod;
    A = Ldiv2[A];
    End;
Return B (possibly removing initial 0’s)

所以对于上面的例子X=169, n=2, B[0] = A[0]%2 = 9%2=1, 那么A=Ldiv2[A] = 84, B[1]=A[0] %2 = 4%2=0 等等。

对于 Ldiv2[A]，我将 4n-1 用于 n > 1，因此根据定义应该为 O(n)，对于算法的运行复杂度，我也将其设置为 O(n)，因为它只有一个 for 循环运行从 0 到 4n -1 虽然有点不清楚是否有证据。

4

1 回答 1

1

我们在一个循环中运行，4n-1每次都执行一个在开始O(n)和O(1)结束时（当 A 变为 1 时）采取的动作。

所以我们得到：

(4n-1)*(n/log(n)) = O(n^2/log(n))
于 2013-09-18T05:26:52.313 回答