このアルゴリズムの時間の複雑さは何ですか？その理由は何ですか？説明付きの次のコードの時間の複雑さ？
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}
正解はO（n）ですが、O（nlogn）を取得しています。誰がなぜそれがO（n）なのか教えてもらえますか？
最初の反復では、内部ループはN回、次にN/2回、次にN/4回などを実行します。これは、無限の和として表現することができます：あなたは、各タームからNを考慮した場合
N + N/2 + N/4 + N/8 + N/16 + N/32 + ...
は、あなたが得る：
カッコ内の無限列が2（詳細は上の値に収束
N * (1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...)
Wikipedia）。そのため、操作の数がに簡素化することができる：ビッグ-Oの面では
N * 2
、漸近値が範囲内である：
O(N)
あなたは出力に関係することを観察することによって、これを確認することができますNとcountの間は線形です：Ideone Demo
試しましたか？立ち往生した場所とその理由を説明してください。これは宿題サービスではありません。 – 4castle
はい、私はしました。問題は、外側ループはO（logn）を実行し、内側ループは外側ループまで実行されるということです。したがって、それはO（nlogn）でなければなりません。しかし、それはO（n）に減らすことができると思います。だから、私は数学的にどのように知りたいですか？ –
はい、これはO（nlogn）にする必要があります。しかし答えはO（n）です。そうです、どうですか？ –