这个带有嵌套循环的函数的复杂性是什么？

Question

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

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)。我说得对吗？

Answer 1

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

您可以使用 Sigma 符号详细分析此问题，以计算每个嵌套循环块的内部循环块中的基本操作数 T_A(n) 和 T_B(n):

我们将 System.out.print ("*"); 操作视为基本操作。

这个带有嵌套循环的函数的复杂性是什么？

What is the complexity of this function with nested loops?

complexity-theory

time-complexity