mid-high-2を計算する修正バイナリ検索の時間複雑度

Question

mid = high-2（mid =（low + high）/ midの代わりにmid = high-2として分割点を計算するバイナリ検索の時間複雑さを調べる必要があります。 2） 修正アルゴリズムがどれほど遅いか速いかを知るため

Answer 1

最悪の場合は、検索された項目が最初のものです。この場合、常にnから2を引くので、線形の複雑さは約n/2ステップになります。最良の場合は、検索されたアイテムが正確にn-2であり、これは一定の複雑さを要することである。 n - >無限大が線形であると仮定した場合の平均複雑度。

Answer 2

ヒント：バイナリ検索の漸化式に基づいて答えを導き出すことができます。

我々は二つの等しいhalfsに分割するので、我々は床（N/2）を有するT（N）= T（床（N/2））+ O（1）

を有します。変更したバージョンを記述するために、指定した数式を書き直す必要があります。さらに、Akra-Bazziメソッドを使用して、2つのアンバランスな半分に分割するので、修正されたバージョンの再帰式を解決する必要があります。