如何定义计算无重复数字下一年的递归代码时间复杂度？

问题背景 #

要计算输入年份的下一个无重复数字的年份，编写了如下递归Python代码，希望明确其时间复杂度：

import math

# Time complexity:
# Space complexity:
def solve(year):
    """ Method to identify the closest year without repeating two digits on it."""
    year_str = str(year)
    if year_str[3] == year_str[0] or year_str[3] == year_str[1] or year_str[3] == year_str[2]:
        year = year + 1
        return solve(year)
    if year_str[2] == year_str[0] or year_str[2] == year_str[1]:
        year = (math.floor(year/10)+1)*10
        return solve(year)
    if year_str[1] == year_str[0]:
        year = (math.floor(year/100)+1)*100
        return solve(year)
    return year

y = int(input())
print(solve(y+1))

测试情况：处理2222年时函数调用4次，处理1987年（结果为2013）时调用8次。

时间复杂度分析 #

这段代码的时间复杂度是O(1)（常数时间复杂度），理由如下：

• 递归调用次数是固定范围内的常数：代码中每次递归要么将年份+1，要么直接跳转到下一个整十数，要么跳转到下一个整百数。对于4位年份来说，哪怕是最坏情况（比如从9999开始），递归调用的总次数也不会超过一个很小的固定值，绝不会随着输入年份的数值大小线性增长。
• 每次递归内部的操作（字符串转换、字符比较、数学运算）都是固定时间的O(1)操作，没有循环或其他随输入规模变化的步骤。

关于代码最优性的补充 #

这段代码已经属于高效实现：通过跳整十/整百的方式跳过了大量无需检查的年份，减少了不必要的调用。如果想要进一步优化，可以用迭代写法替代递归（避免递归栈的微小开销，但对于当前的调用次数来说，实际影响可以忽略）。

内容的提问来源于stack exchange，提问作者Daniel Sanchez