嵌套循环的此功能的复杂性是什么? [英] What is the complexity of this function with nested loops?

问题描述

这段代码的复杂性是什么?

What is the complexity of this code?

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();
   }
} 

}

我的假设是因为n *(n/2)+ n *(n/2)，所以将需要O(n ^ 2)个运算.我说的对吗?

My assumption is that it will take O(n^2) operations because n*(n/2) + n*(n/2). Am I right?

推荐答案

您是正确的，第一个和第二个嵌套循环块都有一个紧密的上渐近界线，例如 T_A(n)和 T_B(n)分别是 O(n ^ 2)，因此该函数作为一个整体运行为 O(n ^ 2)，渐近地.

You are correct, a tight upper asymptotic bound for both the first and second nested loop blocks—say T_A(n) and T_B(n), respectively—is O(n^2), and hence the function as a whole runs as O(n^2), asymptotically.

您可以使用Sigma表示法对此进行详细分析，以对每个嵌套循环块 T_A(n)和 T_B(n)的内部循环块中的基本操作数进行计数:

You can analyze this in detail using Sigma notation to count the number of basic operations in the inner loop blocks for each of the nested loop blocks T_A(n) and T_B(n):

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

Where we've treated the System.out.print ("*"); operation as basic operation.

这篇关于嵌套循环的此功能的复杂性是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！