Python中内嵌random.shuffle的while循环时间复杂度如何？能否衡量？

首先得指出你提供的示例代码有严重问题：sort函数内部的while not sort(numbers)==numbers会触发无限递归，直接导致栈溢出，根本无法正常运行。正确的写法应该是单独实现一个判断数组是否有序的辅助函数，比如：

import random

def is_sorted(numbers):
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i+1]:
            return False
    return True

def sort(numbers):
    while not is_sorted(numbers):
        random.shuffle(numbers)
    return numbers

接下来回答你的核心问题：

时间复杂度的衡量方式 #

这种算法属于拉斯维加斯型随机算法——它总能给出正确结果，但运行时间是随机变量。我们无法用传统的最坏/最好情况时间复杂度来精准描述，但可以用期望时间复杂度来衡量，这是这类随机算法的标准分析方法。

具体复杂度计算 #

1. 单次random.shuffle的时间复杂度是O(n)：它会遍历数组一次，对每个元素进行随机交换操作。
2. 循环的期望次数：对于包含n个不同元素的数组，总共有n!种可能的排列，其中只有1种是我们需要的有序排列（假设目标是升序）。每次洗牌得到有序排列的概率是1/n!，根据几何分布的期望公式（成功概率为p时，期望尝试次数是1/p），循环的期望执行次数是n!。

把两者结合起来，整个算法的期望时间复杂度是O(n × n!)。

关于最坏情况 #

理论上，最坏情况是无限循环（可能永远洗不出有序排列），但这种情况的概率趋近于0，实际讨论中我们更关注有意义的期望复杂度。

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