0

以下算法检查数字是否为素数:

Given a number n,loop over all numbers smaller than n and check whether they divide n. 
If one of them divides n, answer no. Otherwise, answer yes.

现在,我必须在以下两种情况下分析算法执行的除法运算次数与其输入长度的函数关系:

1)数字以一元编码(即4为1111)。如何证明除数是多项式的?

2)数字以二进制编码(即4为100)。我如何证明划分的数量是指数的?

4

2 回答 2

1

假设我们将n 1' 串在一起(标记为1^n)。 n显然是我们输入的长度。我们将把11, 111, ... 中的所有整数1^(n-1)分成1^n. 1^n作为 的函数,您将分成多少个数字n?这是多项式吗?

请注意,用二进制表示大约需要log_2(x)(log base 2 of x) 位。x另请注意,我们将执行x-2除法(2, 3, 4, 5, ... ,x-1将分为x)。因此,对于log_2(x)位,我们使用x-2除法。相反,假设我们让n成为输入的大小。所以我们有n = log_2(x). 那么,根据 的函数,我们将进行多少次划分n

于 2012-04-24T18:03:52.170 回答
0

暗示:

将问题大小定义n为数字的(二进制|一元)表示中的位数。

现在考虑可以用数字编码多少个不同的n数字。

于 2012-04-24T17:45:24.477 回答