如何求解给定嵌套循环算法的时间与空间复杂度

参考代码 #

for( j = 1; j < n ; j = j * 3)
{
    for( k = 1 ; k <= n ; k = k + 2 )
    {
      r = i + j + k ;
      System.out.println(r);
    }
}

时间复杂度计算 #

• 先看外层循环：j从1开始，每轮循环j变为原来的3倍，直到j大于等于n时停止。循环执行次数满足3^t < n，解得执行次数t为以3为底n的对数，大O表示法会忽略对数的底数（不同底数仅差常数系数），所以外层循环的时间量级为O(log n)
• 再看内层循环：k从1开始，每轮循环加2，直到k大于n时停止。不管n是奇数还是偶数，循环执行次数都约为n/2，时间量级为O(n)
• 两层循环是嵌套关系，总执行次数是外层次数乘以内层次数，因此整体时间复杂度为O(n log n)

空间复杂度计算 #

整个算法运行过程中，只用到了j、k、r三个固定数量的临时变量，没有申请和输入规模n成正比的额外存储空间，占用内存不会随n的增大而增长，因此空间复杂度为O(1)，也叫常数空间复杂度。

内容的提问来源于stack exchange，提问作者Arun E.R