咨询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
相关产品推荐
相关产品推荐

