長さの並べ替えられた配列があり、線形検索を使用して値を配列内のすべての要素と比較しています。次に、nサイズの配列で線形検索を実行し、n/2次にのサイズで線形検索を実行します。長さ 1 の配列。この場合、n は 2 のべき乗です。実行される比較の回数は?n/4n/8
この応答が正しいかどうかは正確にはわかりませんが、比較の数は
T(2 n ) = (n/2) +(n/4) + ... + 1.
これについての私の理由は、すべての要素を通過する必要があり、それを追加し続けるためですが、まだわかりません. 誰かが私にこれを教えてくれたら、私はそれを感謝します
n が入力の長さである場合、入力の長さを 2 nで示さないため、質問で設定した繰り返しは少しずれています。代わりに、k の選択に対して n = 2 kと記述します。これを取得したら、次のように計算できます。
これらの値をすべて合計すると、次のようになります。
2 k + 2 k-1 + 2 k-2 + ... + 2 + 1 = 2 k+1 - 1
これはいくつかの方法で証明できます。帰納法を使用したり、等比級数の和の公式を使用したりできます。これはコンピュータ サイエンスで頻繁に発生するため、覚えておく価値があります。
これは、 n = 2 kの場合、アルゴリズムが時間内に実行されることを意味します
2 k+1 - 1 = 2(2 k ) - 1 = 2n - 1
したがって、実行時間は 2n - 1、つまり Θ(n) です。
お役に立てれば！