このネストループのBig-Oとは何ですか？

int z=1; 
for（int i=0;i*i<n;i++）｛ 
    z*=3; 
    for（int j=0;j<z;j++）{ 
    // Some code 
    } 
}

回答はO（3^n）です。正しいですか？どのように入れ子になったループの時間の複雑さを把握するには？このネストループのBig-Oとは何ですか？

2016-10-24 Mr. J

外側ループ：iは1からsqrt（n）になります。内部ループ：j、zは3になります^（sqrt（n））;

"いくつかのコードは、" 1 + 3 + 3^2 + ... + 3 ^（SQRT（N））回

let sum = 1 + 3 + 3^2 + ... + 3^(sqrt(n)) 
sum - 3*sum = 1 - 3(sqrt(n) + 1) 
sum = 1 - 3(sqrt(n) + 1)/(1-3) = 2(3^(sqrt(n)+1) - 1)

2（3 ^（SQRT（N）+1）を実行します

： - 1）< < O（3^SQRT（N））

Oあなたは、Sigma表記にこの方法を使用して、問題に近づくことができた（3^SQRT（n）は）より正確な

2016-10-24 03:05:14 softwarenewbie7331

'3^sqrt（n）'は、外部ループの最後の反復の実行時間であり、実行全体ではありません。 – mangusta

私が提供したシリーズの合計について、より正確な答えを提供することを歓迎します。確かにO（3^n）ではありません。 – softwarenewbie7331

いいえ、あなたの複雑さは正しいです、幾何学的な進行の合計は依然としてO（3^sqrt（n））である 'b1 *（q^n-1）/（q-1）、q =不便をおかけして申し訳ありません。 – mangusta

あります

2016-10-25 16:11:24

答えて