时间复杂度计算的快速解题步骤

指数增长/累加型的循环：可用“假设循环执行k 次，推出退出条件”的方法。

当一个变量 sum 累加到某个值 n 后退出时

1. 外层循环看次数

• for 循环：看循环变量的增长方式，确定执行次数：

  • i++：线性增长，执行 n 次 → O(n)。
  • i∗=2：指数增长，每次翻倍，执行 logn 次 → O(logn)。

• while 循环：看循环变量每次怎么变动，直到结束为止。

2. 内层循环乘上外层的次数

• 嵌套循环时，计算内层循环的复杂度，再乘外层循环的次数
• 内层所有循环次数的总和（这里可能需要用到求和公式）。
  • 简单规则：
    • 外层循环执行 n 次，内层m 次 → 总次数 n×m。

3. 使用数学规律简化

• 如果有求和公式，可以套公式，不需要复杂推导：

4. 忽略常数，留最高次幂

示例：嵌套循环 + 非线性增长

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < i; j++) {
        // O(1) 操作
    }
}

 

---

int sum = 0;
for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < i; j++) {
        sum++;
    }
} 

 等比数列，总和接近 2n−1，丢掉常数就是n

列表格时只考虑主导循环变量，计数变量如 sum 通常只是个累加器，受循环变量控制。

---

int i = 0, sum = 0;
while (sum < n) {
    sum += ++i;
} 

或者想象每次累加的效果：如果 n=10，那你只需要累加到 4（1+2+3+4=10）。

• 这说明循环的次数跟n 的平方根有关。

 

---

x = 0;
while (n >= (x+1) * (x+1)) {
    x++;
} 

 

---

------------------------------------------------------练习题----------------------------------------------------------------

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n / i; j++) {
        sum++;
    }
}

外循环n次，内循环对于每个固定的i，j 的范围是从 1 到 n/i，所以执行n/i 次。把所有的 i 累加起来，总执行次数为： ，这是一个 调和级数，我们知道：

得出结果 O(nlogn)。

原文地址：https://blog.csdn.net/m0_73528660/article/details/143865241

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！