这个除法算法的大 O 复杂度是多少 [英] What is the Big O complexity for this division algorithm

问题描述

Input: Two n-bit integers x and y, where x ≥ 0, y ≥ 1.
Output: The quotient and remainder of x divided by y.
if  x = 0, then return (q, r) := (0, 0);
q := 0;  r := x; 
while (r ≥ y) do
    { q := q + 1;
      r := r – y};
return (q, r);

我已经获得了 O(n^2) 的大 O 复杂度，但朋友说它是 O(2^n)，其中 n 是作为输入大小的位数

I have obtained the Big O complexity as O(n^2) but a friends says it is O(2^n) where n is the number of bits as the input size

请给出解释

推荐答案

while循环的迭代次数正好是floor(x/y).每次迭代需要 n 次操作，因为这是减法 r - y 的复杂度.

The number of iterations of the while-loop is exactly floor(x/y). Each iteration takes n operations, because that is the complexity of the subtraction r - y.

因此算法的复杂度为n * floor(x/y).但是，我们想将复杂性表示为 n 的函数，而不是 x 和 y 的函数.

Hence the complexity of the algorithm is n * floor(x/y). However, we want to express the complexity as a function of n, not as a function of x and y.

因此问题变成:在最坏的情况下，floor(x/y) 与 n 有何关系?

Thus the question becomes: how does floor(x/y) relate to n, in the worst case?

当x和y是两个非负的n时，x/y所能得到的最大值-digits 数字，并且 y >= 1，是通过取 x 的最大可能值和 y 的最小可能值获得的.

The biggest value that can be obtained for x/y when x and y are two nonnegative n-digits numbers, and y >= 1, is obtained by taking the biggest possible value for x, and the smallest possible value for y.

• x 的最大可能值是 x = 2**n - 1(x 的所有位在其二进制表示中都是 1);
• y 的最小可能值是 y = 1.

• The biggest possible value for x is x = 2**n - 1 (all bits of x are 1 in its binary representation);
• The smallest possible value for y is y = 1.

因此 x/y 的最大可能值是 x/y = 2**n - 1.

Hence the biggest possible value for x/y is x/y = 2**n - 1.

你的除法算法的时间复杂度是O(n * 2**n)，当x = 2**n - 1时达到这个上限code> 和 y = 1.

The time-complexity of your division algorithm is O(n * 2**n), and this upper-bound is achieved when x = 2**n - 1 and y = 1.

这篇关于这个除法算法的大 O 复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！