嵌套循環這個函數的複雜性是什麼？

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)，漸近。

可以使用六西格瑪符號來算基本操作在內環塊的數量爲每個嵌套循環塊T_A(n)和T_B(n)的分析對此進行了詳細：

當我們處理作爲基本操作的System.out.print ("*");操作。