Python选择排序函数的时间与空间复杂度分析求助

我刚开始用Python学习算法，需要帮助分析我编写的三个选择排序函数的时间和空间复杂度。我对第三个函数selection_sort3的复杂度存疑，不确定其时间复杂度是否为O(n²)，更不确定空间复杂度是否为O(2n)。我知道返回的新数组会占用额外空间，但想了解每次迭代对长度递减的子数组调用min是否会增加空间占用。

def selection_sort1(array): # Time complexity O(n^2), space O(1)
    length = len(array)
    for i in range(length - 1):  # Loop n - 1 times
        for j in range(i + 1, length):  # Loops n - 1 times
            if array[j] < array[i]:
                array[i], array[j] = array[j], array[i]
    return array

def selection_sort2(array): # Time complexity O(n^2), space O(1)
    for i, k in enumerate(array[:-1]): # Loops n - 1 times
        for j, v in enumerate(array[1 + i:]):  # Loops n - 1 times
            if v < k:
                array[i], array[j] = array[j], array[i]
    return array

def selection_sort3(array):  # Time complexity O(n^2), space O(2n) ????
    result = []
    for i in range(len(array)):  # Loops n times
        result.append(min(array[i:])) # min function walks through the entire array so its complexity is O(n) ???? 
    return result

逐个函数分析 #

selection_sort1 #

• 时间复杂度：确实是O(n²)。外层循环执行n-1次，内层循环每次从i+1遍历到数组末尾，总迭代次数为(n-1)+(n-2)+...+1 = n(n-1)/2，属于O(n²)量级。
• 空间复杂度：O(1)。所有操作都在原数组上完成，仅使用了几个固定大小的变量，没有开辟与输入规模相关的额外存储空间。

selection_sort2 #

• 时间复杂度：O(n²)。外层循环执行n-1次，内层循环遍历的子数组长度递减，总迭代次数同样是n(n-1)/2，符合O(n²)特征。但要注意：这个函数存在逻辑错误，内层enumerate(array[1+i:])返回的j是子数组的索引，不是原数组索引，因此交换操作array[i], array[j] = array[j], array[i]无法完成正确排序。
• 空间复杂度：并非O(1)。array[:-1]和array[1+i:]都是切片操作，会生成原数组的子数组副本，每次切片最大长度为n-1，因此空间复杂度为O(n)。

selection_sort3 #

• 时间复杂度：确实是O(n²)。外层循环执行n次，第i次调用min(array[i:])需要遍历长度为n-i的子数组，总遍历次数为n+(n-1)+...+1 = n(n+1)/2，属于O(n²)量级。
• 空间复杂度：O(n)，而非O(2n)。理由如下：
  1. 返回的result数组长度为n，占用O(n)空间；
  2. 每次调用min时生成的切片临时数组，在min执行完毕后就会被垃圾回收，同一时间仅存在一个临时数组（最大长度为n）；
  3. 渐近复杂度分析忽略常数系数，O(n)+O(n)仍等价于O(n)，因此整体空间复杂度为O(n)。

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