Python嵌套循环函数时间复杂度辨析：O(n²)还是O(n²logn)？

def create(t, m):
    n = len(t)
    while n > 1:
        s = ()
        for i in range(0, n, m):
            minX = t[i]
            for j in range(i+1, min(i+m, n)):
                if t[j] < minX:
                    minX = t[j]
            s = s + (minX,)
        n = len(s)
        t = s
        print(t)
    return t

示例调用：

print(create((11,9,10,6,7,8,5,4,3,2,1), 3))

题目要求基于输入元组t的长度n（m为2-9的正整数，n远大于m）分析代码时间复杂度。我认为是O(n²logn)，但参考答案为O(n²)，具体分析如下：

我的分析理由 #

while循环执行次数随n缩减呈对数级（每次n近似减半），需计入logn因子。外层for循环（i步长为m）每次迭代次数为O(n)，嵌套内层for循环最坏情况为O(n)，因此总复杂度应为O(n×n×logn)。

官方参考答案 #

复杂度为O(n²)，因m是常数。两层for循环总时间为线性级（n + n/m + n/m²+... <2n），耗时由语句s = s + (minX,)主导，各轮while循环中该语句总时间为O((n/m)²)+O((n/m²)²)+...，求和后仍为O(n²)。

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