You need to enable JavaScript to run this app. 咨询C++数组K个连续元素最大和函数的大O时间复杂度
优惠活动
大模型
产品
解决方案
定价
更多

咨询C++数组K个连续元素最大和函数的大O时间复杂度

K连续元素最大和函数的时间复杂度咨询

我编写了用于计算数组中K个连续元素最大和的C++函数,该函数接收数组、数组长度、待统计的连续元素个数K作为入参,通过遍历数组求解目标值,现咨询该函数的大O(Big-O)时间复杂度是多少,具体实现代码如下:

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int GetLargestSum(int array[], int length, int k)
{
    int largestSum = 0;
    int previousSum = 0;
    for (int i = 0; i <= length - k; i++){
        if (i == 0){
            for (int j = 0; j < k; j++){
                largestSum += array[j];
            }
            previousSum = largestSum;
        } else{
            int currentSum = previousSum - array[i - 1] + array[i + k - 1];
            if (currentSum > largestSum){
                largestSum = currentSum;
            }
            previousSum = currentSum;
        }
    }
    return largestSum;
}

int main(){
    int k = 3;
    int array[] = {1, -3, 4, 1, 7, -5, 9};
    cout << "Largest sum of " << k << " consecutive elements of an array = " << GetLargestSum(array, 7, 3);
}

逐段复杂度拆解

按代码实际执行流程统计操作量级:

  • 外层主循环的遍历边界为i从0到length - k,总触发次数为length - k + 1次
  • 仅在i=0的首次循环中,会触发内层循环计算第一个大小为k的窗口的初始和,这部分操作量为k次,且仅执行一次,不会随外层循环重复触发
  • 从i=1开始的所有循环分支,均为常数级操作:从上一轮缓存的窗口和中减去移出窗口的旧元素、加上移入窗口的新元素、对比更新全局最大和,每轮循环固定消耗常数时间O(1),总共触发length - k次

将所有操作量加总后,总执行步数为k + (length - k)*1 = length,完全与数组总长度同阶。

易混淆点说明:如果是暴力实现的版本,每移动一次窗口都要重新遍历k个元素求和,总操作量为(length -k +1)*k,复杂度为O(N*K);但当前实现复用了上一轮的窗口和,没有重复遍历累加元素,不存在嵌套乘级的操作量。

最终复杂度结论

  • 该函数的大O时间复杂度为 O(N),其中N是传入的数组总长度
  • 复杂度与入参K的取值无线性关联,哪怕K的数值接近数组总长度,整体操作量也始终和数组长度保持同级别线性增长

内容的提问来源于stack exchange,提问作者Lockdock

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.12 07:45:04