これらの2つのネストされたforループの時間の複雑さはどのくらいですか？

-1

このコードの時間複雑さはO（N ）であることがわかりました。そうですか？これらの2つのネストされたforループの時間の複雑さはどのくらいですか？

2016-09-16 Avenger

for(i=n;i>=1;i--) { 
    for(j=n-i; j>=1; j--) { 
    x++; 
    } 
}

はい、それはO（N 2 ）です。

外側ループはn回実行されます。内側のループは、平均してn/2回実行されます。内側ループと外側ループの複雑さを掛け合わせて、O(n * n/2)を得る。これはO（n ）である。

出典

2016-09-16 11:33:52 kfx

秒ループはどのようにn/2回実行されますか？ n-1回実行されます。ではない？もしそうなら、それでは説明してください。 – Avenger

外部ループが最初に入力されるとき、「i」は「n」に等しいので、内部ループはまったく実行されません。次に 'i'が' n-1'に等しいので、 'x ++'が1回実行されます。その後、2回、3回、4回、 'i = 1 'になるまで、' n-1'回実行されます。数の平均は1,2、...、n-1はO（n/2）のオーダである。 – kfx

もう1つの見方は、1、2、... n - 1の合計はn乗の項を持ち、orderはO（n^2） –

これらの2つのネストされたforループの時間の複雑さはどのくらいですか？

答えて

関連する問題