このアルゴリズムの複雑さは何ですか

このアルゴリズムの時間複雑度はどのくらいですか？このアルゴリズムの複雑さは何ですか

void prime(int n) { 
    int i = 2; 
    while ((n % i) && i <= sqrt(n)) 
     i++; 

    if (i > sqrt(n)) 
     print(“%d is a prime number\n”, n); 
    else 
     print(“%d is not a prime number\n”, n); 
}

出典

2016-09-13 Vincent_Bryan

なぜ「n」が素数であるか素数でないと複雑さが変わると思いますか？ – Paul

yap、nは素数でもなくても複雑さは変わらないことを知っています。だから私はその複雑さについて全く知らない。 –

だから、あなたは何を求めているのですか？あなたのコメントはあなたの質問の最初の行と直接矛盾します。 –

私は間違っていました。ちょっとO（sqrt（n））... すべてのxに対してcontionが実行されるのを見てください。< = nを分けるsqrt（n）。だから私はatmostほとんど実行することができます（sqrt（n））回。ですから、それはO（sqrt（n））です。その他の要因はありません。

出典

2016-09-13 02:55:33 coderredoc

@Vincent_Bryan ::そのearllierのようにして申し訳ありません...私の答えを今確認してください。それはsqrt（n）です。 – coderredoc

私はO（sqrt（n））が悪いケースだと思いますが、平均的なケースは何ですか？ –

複雑さは約O（sqrt（N））です。 O（N ^0.5）と書かれている本もあります。

ループの各繰り返しが平方根で再計算されます。これはかなり遅い操作なので、最適なものよりも遅いですが、定数だけで済むので、計算の複雑さには影響しません。

出典

2016-09-13 04:03:03

これはC++固定サイズの整数なので、そうです。 sqrtは、例えばそれが一定であった場合には一定である必要はないが。 Python、または数学ライブラリからの大きな整数型です。 –

このアルゴリズムの複雑さは何ですか

答えて

関連する問題