入れ子ループの時間複雑さは親ループに依存する

Question

次のコードのT（n）を見つける方法。私は分析が必要です。

void abc(int n) { 
    for(int i = 0; i<n; i++){ 
    for(int j = 0; j<i; j++){ 
     System.out.println("Hello World"); 
    } 
    } 
} 

Answer 1

複雑さはO（N^2）です。

詳細には、計算の次のとおり

T（N）= 1 + 2 + 3 + ... + N = N（N + 1）/ 2

だからO（N^2）

Answer 2

プログラム内のループの複雑さを計算するには、プログラム内のnumberループ宣言をチェックしてから、ネストして呼び出しの深さを確認します。

このコードでは、複雑さは1つのループと別の内部ループによって発生するため、O（N^2）になります。

しかし、outerloopはn個連続しており、内側ループはi + 1であるため、順次1 + 2 + 3 ... nとなるため、n *（n + 1）/ 2として計算されます、最終的にはO（N^2）につながります。