逐次相减实现的除法算法的Big O复杂度是O(n²)还是O(2ⁿ)？

你朋友的结论更符合输入规模为比特数n时的复杂度定义，你的O(n²)结论大概率是混淆了输入规模的定义，或是将该朴素累减算法与更高效的位运算除法算法搞混了，详细推导如下：

1. 核心前提明确 #

• 输入规模：题目定义输入为两个n-bit整数，即x的取值范围是0 ≤ x ≤ 2ⁿ - 1，y的取值范围是1 ≤ y ≤ 2ⁿ - 1，输入规模为比特数n，而非x、y的数值大小。
• 复杂度计数默认采用RAM单位成本模型：即两个整数的比较、加减运算都视为原子操作，耗时为常数O(1)。

2. 最坏场景确定 #

该算法的时间开销完全由while循环的执行次数决定，循环的触发条件是当前余数r ≥ y，每次循环r固定减少y。
最坏情况出现在y取最小值1时：此时初始余数r = x，每次循环r仅减少1，循环执行的总次数等于x的数值大小。

3. 复杂度计算 #

n-bit无符号整数的最大值为2ⁿ - 1，所以最坏情况下循环执行次数为2ⁿ - 1，即O(2ⁿ)次。
结合单位成本模型下每次循环操作耗时O(1)，总时间复杂度为O(2ⁿ)，这就是你朋友结论的来源。

4. O(n²)结论的误区说明 #

你算出的O(n²)通常是位运算实现的长除法的时间复杂度，和本题的朴素累减算法完全不同：

• 长除法每次迭代处理1个比特位，总共只需要循环n次，每次循环执行O(n)比特级操作，总复杂度为O(n²)。
• 如果你误将输入规模定义为x的数值大小（设为M），那该算法的复杂度是O(M)，如果再错误地把M和n等同（比如把n当成数值而非比特数），也会得到错误的O(n)甚至O(n²)的结论。
  如果采用比特操作计数（每次单比特运算算O(1)），该朴素算法的每次循环的减法、比较操作都需要O(n)时间，总复杂度为O(n * 2ⁿ)，也远高于O(n²)。

内容的提问来源于stack exchange，提问作者Azam M