咨询mysort1与mysort2函数的时间复杂度判定是否正确

先看mysort1：

• y = list(x)：复制输入序列，时间复杂度O(n)
• y.sort()：Python内置排序采用Timsort算法，时间复杂度O(n log n)，这是整个函数里复杂度最高的步骤
• z = [0]*len(y)：创建固定长度列表，O(n)
• 循环执行z[i] = y[i]：每个赋值是常数时间，循环n次总复杂度O(n)

所以mysort1的整体时间复杂度由排序步骤主导，是O(n log n)——你之前认为的O(n)不对，因为排序的复杂度远高于线性操作，会覆盖掉其他步骤的线性开销。

再看mysort2：

• 前两步和mysort1一致：y = list(x)为O(n)，y.sort()为O(n log n)
• 核心差异在循环里的z.insert(0, y[len(y)-i-1])：列表是动态数组结构，在头部插入元素时，需要把现有所有元素向后移动一位，每次插入的时间复杂度和当前列表长度成正比。第一次插入耗时O(1)，第二次O(2)……第n次O(n)，总操作次数是1+2+…+n = n(n+1)/2，对应时间复杂度O(n²)

这个O(n²)的步骤复杂度远高于排序的O(n log n)，所以mysort2的整体时间复杂度是O(n²)。

总结：

• mysort1：O(n log n)
• mysort2：O(n²)

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