这个带有嵌套循环的函数的复杂度是多少？

这段代码的复杂度是多少？

public class test5{
public static void main(String[] args) {
   int n = Integer.parseInt(args[0]);
   for (int i = 1; i<=n; i++) {
      for (int j = 1; j<=i; j++) {
         System.out.print ("*");
      }
   System.out.println();
   }

  for (int i = n; i>=1; i--) {
      for (int j = 1; j<=i; j++) {
         System.out.print ("*");
      }
   System.out.println();
   }
} 

}

我的假设是需要 O(n^2) 次操作，因为 n*(n/2) + n*(n/2)。 我对吗？

你是对的，第一个和第二个嵌套循环块都有一个严格的渐近上界——比如说T_A(n) and T_B(n)，分别是O(n^2)，因此函数作为一个整体运行为O(n^2)，渐近。

您可以使用 Sigma 表示法来详细分析每个嵌套循环块的内部循环块中的基本操作数T_A(n) and T_B(n):

我们治疗过的地方System.out.print ("*");操作作为基本操作。