求给定递归函数hello的时间复杂度分步分析方法

待分析代码 #

int hello(int n){
   if(n==0)
       return 0;
   for(int i=0;i<n;i++){
      for(int j=0;j<n * n;j++){
         System.out.println("HELLO");
      }
   }
   return hello(n-1);
}

分步计算过程 #

• 步骤1：计算单次hello(n)调用非递归部分的时间复杂度
  单次调用时，两层循环的执行次数：外层循环共执行n次，内层循环每次执行n²次，总循环操作次数为n * n² = n³，因此单次调用非递归部分的复杂度为O(n³)。
• 步骤2：建立递归递推关系式
  递归终止条件为n=0，此时仅执行常数次操作，记为T(0) = O(1)。
  当n>0时，总时间 = 单次非递归部分时间 + 递归调用hello(n-1)的时间，因此递推式为：
  T(n) = T(n-1) + O(n³)
• 步骤3：展开递推式求和
  将递推式逐层展开可得：
  T(n) = n³ + (n-1)³ + (n-2)³ + ... + 1³ + T(0)
  前n个正整数的立方和有通用公式：1³ + 2³ + ... +n³ = [n(n+1)/2]² = (n⁴ + 2n³ +n²)/4
  如果不记得立方和公式，也可以用缩放法估算量级：前n个项每个都不超过n³，总和上限为n * n³ = n⁴；前n个项中至少有n/2个项不小于(n/2)³，总和下限为(n/2) * (n/2)³ = n⁴/16，因此总和的量级为n⁴。
• 步骤4：确定最终复杂度
  忽略低次项和常数系数，总时间复杂度为O(n⁴)。

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