求n位整数迭代除法算法的时间复杂度（以n为计算单位）

问题前提 #

• 输入：两个n位整数x和y，其中y ≥ 1
• 输出：x除以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);

时间复杂度计算 #

默认此处的n为整数的二进制位数，n位二进制无符号整数的取值范围为 [2^(n-1), 2^n - 1]，复杂度分析如下：

1. 单次循环操作复杂度：循环内的核心操作是两个n位整数的减法运算，需要逐位处理两个数的每一位，因此单次循环的时间复杂度为 O(n)，和代码注释的说明一致。
2. 循环迭代次数：最坏情况出现在y取最小值1时，此时需要反复执行x次减法才能让余数r小于y，x作为n位整数最大值为 2^n - 1，因此最坏迭代次数为 O(2^n)。（注：代码注释中提到的“最坏n次迭代”不符合该朴素减法除法的实际迭代次数，该描述更符合移位实现的长除法的迭代次数，本算法为反复做减法的朴素实现，迭代次数和整数的数值规模成正比。）
3. 总时间复杂度：单次循环复杂度乘以迭代次数，最终最坏时间复杂度为 O(n·2^n)，属于指数级复杂度。

内容的提问来源于stack exchange，提问作者Sachin Murthy