は私が与えられてきた再帰

Question

を使用して、配列内の要素の出現回数を数える次のプロンプト

がAを分割することによりvが配列Aで発生した回数をカウント再帰関数を作成します。毎回2つのサブアレイに分割する。

BinarySearchを使用するよりも、これにアプローチする方が良いでしょうか？これは動作しますので、私はこの部分での検証を必要としない

int count(int *A, int low, int high, int v) { if(low > high) return 0; int total = 0, mid = (low + high)/2; if(A[mid] == v) total++; return count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v); }

：私は次の関数を作成しました。

アレイAがソートされているかどうかはわかりませんので、配列Aの左半分と右半分の両方を検索する必要があります。しかし、私は書いた関数の時間の複雑さを見いだす必要があります。私が考えていることは次のとおりです。

変数の割り当てはO(1)なので、考慮する必要がある部分はcount(A, low, mid - 1, v) + total + count(A, mid + 1, high, v)です。

T(n) = T(n/2) + O(1) + T(n/2) = 2T(n/2) + O(1)、

私たちは私たちを与えるために、マスターの定理を使用することができます。私たちは2の部分問題の大きさと2部分に配列を分割しているので、私は次の漸化式を作成しましたT(n) = O(n)。私の質問：変数の割り当てはO(1)で一定であり、count関数の各部分はT(n/2)が有効であると私は仮定していますか？

配列全体のn要素をチェックする必要があるため、O(n)の全体的な複雑さは理にかなっています。

Answer 1

答えに「はい」と書いて、受け入れられた短い答えを目指しました。

しかし、アルゴリズム分析で最も一般的に使用される計算モデルでは、log(n)ビットを含むすべての操作は、O(1)時間で実行されると想定されています。これは、配列が極端に大きく（例えば2^n）、値自体が非常に大きい場合を除き、すべての操作がO(1)時間で実行できると想定しても安全です。

T(n/2)に関する分析では、各再帰呼び出しで配列の長さを単純に半分にしているので、正しいとは言えません。