Python递归实现唯一元素列表算法的时间复杂度分析

先贴出你的实现代码：

def is_unique(nums: list[int], first=0, second=0) -> bool:
    if first == len(nums) - 1 and second == len(nums) - 1:
        return True
    else:
        if second == len(nums):
            first += 1
            second = 0
        if first != second and nums[first] == nums[second]:
            return False
        return is_unique(nums, first, second + 1)

时间复杂度分析 #

你的判断是对的，最坏情况下时间复杂度为O(n²)。

这个递归函数的核心逻辑是遍历所有(first, second)的索引组合，检查是否存在非同一位置但元素值重复的情况：

• 当列表所有元素都唯一时（最坏场景），函数必须遍历完所有可能的索引组合才会返回True。
• 总共有约n²次递归调用，每次调用内部仅做常数时间的条件判断和变量更新，因此整体时间复杂度为O(n²)。

空间复杂度分析 #

你对空间复杂度的判断同样正确，最坏情况下为O(n²)。

Python默认不支持尾递归优化，每次递归调用都会在调用栈中生成一个新的栈帧：

• 最坏场景下（所有元素唯一），递归调用的总次数为O(n²)，且调用栈的最大深度等于总调用次数（每个调用必须等待下一层调用返回后才会弹出栈帧）。
• 每个栈帧仅占用常数空间，因此整体空间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者Miguel Cruz Santiago