for循环内嵌套含ArrayList.contains的while循环的时间复杂度如何计算

首先明确代码中两个核心组件的基础开销特性：

• 外层循环遍历list的总迭代次数等于list的长度，记为n，每轮循环初始化变量、读取列表元素的操作都是常数级时间开销，不随列表规模变化。
• ArrayList的contains()方法本质是全列表线性扫描：每一次调用该方法，都需要将待查询的cur和当前output中已存储的所有字符串逐个做相等比较，单次调用的时间开销和当前output的元素个数成正比。

再拆解while循环的实际运行行为：

• while循环的作用是为重名字符串追加数字后缀完成去重，在常规业务场景下，单轮外层循环的while迭代次数是极低的常数：绝大多数情况下，第一次生成的带数字后缀的字符串就不会和已有元素重名，循环会直接跳出，不会出现随n规模增长的迭代次数。

核心复杂度推导 #

外层循环执行到第i轮时，output里已经累计存了i个之前添加的字符串。这时候哪怕while循环只执行1次contains()判断，单步操作的扫描范围就是全部i个已存元素，开销和i成正比。
把所有轮次的开销加总：从第0轮到第n-1轮，每轮的扫描开销大概是固定系数乘以i，最终总开销就是等差数列求和的结果c * n(n-1)/2，对应整体O(n²)的时间复杂度。

你关注的while循环内的output.contains(cur)操作，正是构成这个二次方复杂度的核心来源：这部分的线性扫描开销，随着轮次推进不断累加，最终形成了二次方规模的总耗时。如果将output从ArrayList替换为HashSet，contains()操作就会变成均摊O(1)的哈希查询，整个算法的时间复杂度会直接降到O(n)。

另外补充边界说明：因为代码中生成的字符串是固定格式（前5位截取字符加数字后缀），单次字符串相等比较是常数时间，不会因为字符串长度变化带来额外的扫描开销，因此不会出现比n²更高阶的时间复杂度。

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