关于O(n²)复杂度括号匹配算法通过力扣等平台测试的疑问

问题背景 #

我原本打算用栈实现经典的括号匹配问题，结果尝试了一种朴素算法，代码如下：

def balanceada(string):
    while True:
       before = len(string)
       string = string.replace('()','')
       string = string.replace('[]','')
       string = string.replace('{}','')
       after  = len(string)
       if after == 0: return True
       if after == before: return False

没想到这个算法居然通过了HackerRank和LeetCode上的对应题目。现在有两个问题需要解答：

1. 该算法的时间复杂度确实是O(n²)吗？比如对于((()))这类多层嵌套的括号案例。
2. 是否存在能检测出该算法超时的在线平台，能展示给学生看O(n²)复杂度的解法会被面试系统拒绝？我可以自己写时间测试，但更希望展示实际面试系统的超时判定结果。

问题解答 #

1. 时间复杂度分析 #

这个算法的时间复杂度确实是O(n²)，以((()))这类嵌套案例为例：

• 第一次循环：替换最内层的()，字符串从长度6变为4，replace操作需要遍历整个字符串，耗时O(n)；
• 第二次循环：替换新的内层()，字符串长度从4变为2，同样耗时O(n)；
• 第三次循环：替换最后一对()，字符串长度变为0，耗时O(n)；
• 总共需要n/2次循环，每次循环都是O(n)级别的操作，整体时间复杂度为O(n²)。

对于极端情况，比如长度为n的完全嵌套括号串（如((((...))))），循环次数与每次遍历长度的乘积最终呈现平方级增长，完全符合O(n²)的复杂度特征。

2. 可检测超时的在线平台 #

可以尝试以下在线评测平台：

• Codeforces：部分题目设置了严格的时间限制，当测试用例规模达到1e5级别时，O(n²)的解法必然超时。可查找括号匹配相关进阶题目，或自行构造大规模测试用例提交；
• AtCoder：平台的时间限制同样严格，不少入门到中级题目会针对低效解法设置超时测试用例；
• POJ（北京大学在线评测系统）：经典在线评测平台，大量基础算法题的测试用例规模足够大，能够卡掉O(n²)的解法。

在这些平台上，提交该朴素算法并使用极端测试用例（如长度1e5的完全嵌套括号串），就能直观展示超时判定结果。

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