嘿，我来帮你理清这两个算法的时间复杂度，咱们一个一个来拆解：

Algorithm 1： #

先贴出代码：

int i=0, j=0, sum = 0; 
while (i*i < n) { 
    while (j*j < n) { 
        sum = sum + i * j; 
        j = j+2; 
    } 
    i = i+5; 
}

你的初步推测O(√n)是对的，咱们来拆解原因：

• 首先注意j只在外部初始化了一次：第一次进入外层循环时，内层循环会让j以步长2递增，直到j*j >=n，这时候内层循环执行的次数大约是√n / 2，也就是O(√n)级别的。
• 之后每次外层循环让i以步长5递增，直到i*i >=n，外层循环的总次数是√n /5，也是O(√n)级别，但此时j已经满足j*j >=n，所以后续的外层循环里，内层循环根本不会执行。
• 总执行次数就是第一次内层循环的O(√n)加上后续外层循环的O(√n)次空操作，整体时间复杂度还是O(√n)。

Algorithm 2： #

对应的代码如下：

sum = 0; 
for (i=0; i<=n; i++){ 
    j = n; 
    while (j>i) { 
        sum = sum + j - i; 
        j = j – 1; 
    } 
}

这个嵌套循环的时间复杂度是O(n²)，推导过程如下：

• 外层循环从i=0到i=n，总共执行n+1次，也就是O(n)级别的次数。
• 对于每个i，内层循环的j从n开始递减到i+1，执行的次数是n - i次：
  • 当i=0时，内层执行n次；
  • 当i=1时，内层执行n-1次；
  • ...
  • 当i=n时，内层执行0次。
• 总执行次数就是求和：n + (n-1) + (n-2) + ... + 0 = n(n+1)/2，这个式子的主导项是n²/2，忽略常数系数后，时间复杂度就是O(n²)。

内容的提问来源于stack exchange，提问作者Kelvin G.M.