为何大小为K的最大子数组和暴力算法时间复杂度是n*k而非(n-k)*k？

首先先算清楚精确的操作次数：

• 数组长度为n时，外层循环会执行n - k + 1次（比如n=5，k=2，循环次数是4次：i=0,1,2,3）
• 每一次外层循环里，内层循环都会执行k次加法操作
• 总操作次数就是k*(n - k + 1) = nk - k² + k

那为什么参考答案标注为O(nk)而不是O((n-k+1)k)？核心在于大O表示法的规则：
大O关注的是当输入规模n趋近于无穷大时，算法执行时间的增长趋势，会忽略掉低阶项和常数系数。这里的-k²和k都是低阶项（当n足够大时，它们和nk比起来可以忽略），所以最终只保留最高阶的nk，复杂度表示为O(nk)。

举个实际的例子：

• 如果n=100000，k=100，(n-k+1)*k ≈ 100000*100 = 10^7，和nk的数值几乎没差别
• 就算k接近n，比如k=90000，(n-k+1)*k ≈ 10001*90000 ≈ 9*10^8，而nk=100000*90000=9*10^9，两者虽然数值有差距，但都是O(n²)的量级，属于同一复杂度类别。

所以用O(nk)来表述是大O表示法下的标准简化，它准确反映了算法的渐近增长趋势，而(n-k+1)k只是精确的操作次数，不是复杂度的标准表述。

对应的代码片段：

def max_sub_array_of_size_k(k, arr):
    max_sum = 0
    window_sum = 0

    for i in range(len(arr) - k + 1):
        window_sum = 0
        for j in range(i, i+k):
            window_sum += arr[j]
        max_sum = max(max_sum, window_sum)
    return max_sum

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