求解给定C++程序的时间复杂度：已完成部分推导，求后续方法

代码示例 #

long long foo(long long n) {
    long long i = 0;
    while (i < n) {
        if (i % 5 == 0) {
            i = i + 6;
        }
        else if (i % 5 == 1) {
            i = i + 1;
        }
        else if (i % 5 == 2) {
            i = i + 16;
        }
        else if (i % 5 == 3) {
            i = i + 11;
        }
        else if (i % 5 == 4) {
            i = i + 21;
        }
   }
}

分析步骤 #

1. 定位循环周期与i的增量规律
   从你列出的i序列：0,6,7,23,34,55,61……可以看出，每5次循环迭代构成一个完整周期：

   • 周期内i的变化路径：0→6→7→23→34→55
   • 单个周期的总增量：55 - 0 = 55，即每完成5次迭代，i总共增加55。

2. 推导总迭代次数
   设循环总迭代次数为T(n)：

   • 每5次迭代对应i增长55，平均每次迭代i的增量为 55/5 = 11；
   • 当n足够大时，总迭代次数近似为 n/11；
   • 即使存在不完整的收尾周期（最多5次迭代，属于常数级开销），对整体复杂度无影响。

3. 时间复杂度结论
   总迭代次数T(n) = Θ(n)，因此该程序的时间复杂度为 O(n)。

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