含三层嵌套循环代码的Big-O时间复杂度计算问题咨询
2026-9-29
代码时间复杂度分析
你的初步判断O(NKC)不正确，实际时间复杂度为O(N*K²)，推导过程如下：
- 最外层循环：
for (int m=0; m < size; m++)共执行N次（N对应参数size），量级为O(N) - 次外层循环：
for (int i = k; i > 0; --i)共执行K次，每轮i的取值依次为K、K-1、……、1 - 类循环：
for (int c = 0; c < 2; ++c)固定执行2次，属于常量级操作，不会影响复杂度量级 - 最内层循环：
for (int j = 0; j < i; ++j)每轮执行次数等于当前的i值，所有轮次加起来的总执行次数为K + (K-1) + (K-2) + …… +1 = K*(K+1)/2，量级为O(K²)
你提到的C在当前代码中固定为2，属于可忽略的常量系数，你之前的推导错误是没有统计到最内层j循环的执行次数和K成平方级关系，误以为内层循环只有固定的常量开销。
额外说明：如果K是业务侧预先固定的小常量（比如KNN场景下固定K=10），那么K²也属于常量系数，整体时间复杂度可以简化为O(N)。
内容的提问来源于stack exchange，提问作者JOJO
相关产品推荐
相关产品推荐
