为何我的容斥类问题解法出现Time Limit Exceeded（TLE）？

我参加了Starters 99赛事，遇到了Codechef上的ONEFROMK问题。最初的解法逻辑正确，但出现了Time Limit Exceeded（TLE），代码如下：

for j in range(int(input())):
     n=int(input())
     arr=sorted(list(map(int,input().split())))
     lst=[]
     for k in range(1,n+1):
         lst.append(sum(arr[k-1:]))
     print(" ".join(list(map(str,lst))))          

最新可通过的解法代码如下：

for i in range(int(input())):
    l=int(input())
    arr=sorted(list(map(int,input().split())))
    s=sum(arr)
    n=[s]
    for k in range(0,l-1):
        s-=arr[k]
        n.append(s)
    print(" ".join(list(map(str,n))))

两种解法的核心差异与TLE原因 #

第一种解法的时间消耗问题

第一种解法的关键问题在于循环内重复计算子数组的和：

• 每次执行sum(arr[k-1:])时，Python都会遍历从索引k-1到数组末尾的所有元素，把它们加起来。
• 假设数组长度是n，第一次循环要算n个元素的和，第二次算n-1个，直到最后一次算1个元素的和。总操作次数是n + (n-1) + ... + 1 = n(n+1)/2，这对应O(n²)的时间复杂度。

当n很大时（比如题目测试用例的n可能达到1e5级别），总操作次数会变成几十亿次，远远超出程序的时间限制，直接导致TLE。

第二种解法的优化逻辑

第二种解法用了逆向累加的思路，把重复计算降到最低：

• 先一次性算出整个数组的总和（只需要遍历数组1次，O(n)操作）。
• 之后每次只需要减去数组前面的一个元素，就能得到下一个子数组的和（每次循环只是1次减法，总共n-1次操作）。
• 总操作次数是n + (n-1) = 2n-1，对应O(n)的时间复杂度。

同样是n=1e5的情况，第二种解法只需要约2e5次操作，和第一种的5e9次操作比，效率差了几万倍，自然能通过时间限制。

给高中刚毕业的你的时间复杂度直白解释 #

你已经知道大O符号的定义，这里再直白点说：

• O(n²)意味着，当输入规模n翻倍时，程序运行时间会变成原来的4倍；n变成10倍，时间变成100倍，增长速度极快。
• O(n)意味着，n翻倍，时间也只翻倍，增长速度平缓，能处理大得多的输入。

这就是为什么第一种解法会超时，而第二种能通过的核心原因。

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