判断整数除法算法的最坏时间复杂度：O(n)是否正确？

先看这段要求a>0，b>0的正整数除法C代码：

int div(int a, int b) {
    int count = 0;
    int sum = b;
    while (sum <= a) {
        sum += b;
        count++;
    }
    
    return count;
}

我在判断它的最坏情况时间复杂度时，给出的答案是O(n)——理由是当b=1时，while循环会执行a次，此时时间复杂度为O(a)，我认为O(a)等价于O(n)（括号内的字母无关紧要）。但书中给出的答案是O(a/b)，这个结果显然合理，不过我想确认：O(n)这个答案是否也正确？

解答 #

• O(n)这个答案不算严格正确，因为时间复杂度的表示需要明确和问题输入参数的关联。这里的核心输入是a和b，O(a/b)能准确反映循环执行次数与两个输入变量的直接关系。
• 你提到的最坏情况（b=1时O(a/1)=O(a)）是对的，但直接写O(n)的问题在于：n没有明确对应到输入中的a。如果没有额外说明n代表a，这个符号就缺乏上下文，无法让读者直接理解它和输入参数的关联，存在歧义。
• 在算法分析的专业场景中，时间复杂度的符号应该尽可能清晰地绑定到输入规模的变量，这样才能准确传达算法的性能特性。因此书中给出的O(a/b)是更严谨、标准的答案，而未明确n含义的O(n)不能算作正确的专业表述。

内容的提问来源于stack exchange，提问作者Serhii Chernikov