如何计算含排序及循环内sum操作的代码总时间复杂度？

先看你提供的代码：

my_list.sort()
runningSum=0
for idx,query in enumerate(my_list):
    runningSum+=sum(my_list[:idx])

接下来拆解各部分的时间消耗：

• 排序操作：my_list.sort() 的时间复杂度是 O(n log n)（n 为列表长度）。
• 循环与求和部分：
  • 外层 for 循环会执行 n 次。
  • 每次循环中，sum(my_list[:idx]) 需要遍历前 idx 个元素，时间复杂度为 O(idx)。把所有循环的时间加起来，就是 0 + 1 + 2 + ... + (n-1)，求和结果为 n(n-1)/2，对应的时间复杂度量级是 O(n²)。

时间复杂度分析取各部分的最高量级——O(n²) 的增长速度远快于 O(n log n)，因此这段代码的总时间复杂度为 O(n²)。

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