フィボナッチ探索
フィボナッチ探索は、効率的な区間探索アルゴリズムです。分割統治法に基づいており、配列をソートする必要があるという意味では、二分探索に似ています。さらに、両方のアルゴリズムの時間的複雑さは対数的です。フィボナッチ級数を利用することからフィボナッチ探索と呼ばれている(現在の数は 2つの前任者の和 F[i] = F[i-1] + F[i-2]、F[0]=0 & F[1]=1 は系列の最初の 2つの数である)が、配列をフィボナッチ数で与えられた大きさの 2つの部分に分割することから、フィボナッチ探索と呼ばれている. 2 進数探索で必要な除算・乗算・ビットシフトに比べて、足し算・引き算だけで済む計算しやすい方法です。
フィボナッチ探索アルゴリズム
n 要素を含むソートされていない配列 A[] があると仮定して、要素 - X を求めよう。
-
配列
nの大きさ以上のフィボナッチ数の最小値を求めよ。この数を m番目のフィボナッチ数fib(m)とし、その前身のfib(m-1)、fib(m-2)とする。 -
オフセットを
-1に初期化する。 -
fib(m-2)が0より大きいときは、以下のようにする。Xとfib(m-2)の最後の要素を比較します。これはA[min(offset + fib(m-2), n - 1)]で与えられます。Xがこの要素と等しければ、そのインデックスを返します。- 逆に、
Xがこの要素より小さければ、この要素の後の半分を破棄し、フィボナッチ数列を 2 ステップ後退させる。また、オフセットを更新して探索空間の開始インデックスを変更します。これらのステップは、配列の探索空間の後方 2/3 を破棄します。 - 逆に、
Xがこの要素より大きければ、この要素より前の半分を破棄し、フィボナッチ数列を一歩後退させる。このステップでは、配列の探索空間の前方 3 分の 1 が破棄されます。
-
fib(m-1)が1に等しい場合は、チェックを外した要素が一つ残っているので、それをXと比較する。 -
どれも一致する要素がなければ、
-1を返す。
フィボナッチ探索の例
配列があるとしましょう。(1, 2, 3, 4, 5, 6, 7). 要素 X = 6 を探さなければならません。
配列には 7つの要素があります。n より大きいフィボナッチ数の最小値は 8 です。
-
fib(m)=8、fib(m-1)=5、fib(m-2)=3が得られる。 -
最初の繰り返し
- 要素のインデックスを
min(-1 + 3, 6)として計算すると、要素はA[2] = 3となります。 3<6すなわち、A[2]<Xなので、A[0.... 2]を破棄し、offsetを2とします。- また、フィボナッチ数列を更新して
fib(m-2)を2に、fib(m-1)を3に、fib(m)を5に移動します。
- 要素のインデックスを
-
二回目の繰り返し
- 要素のインデックスを
min(2 + 2, 6)として計算すると、要素はA[4] = 5となります。 5<6すなわち、A[4]<Xなので、A[2 .... 4]を破棄し、offsetを4とします。- また、フィボナッチ数列を更新して
fib(m-2)を1に、fib(m-1)を2に、fib(m)を3に移動します。
- 要素のインデックスを
-
三回目の繰り返し
- 要素のインデックスを
min(4 + 1, 6)として計算すると、要素はA[5] = 6となります。 6==6、すなわちA[5]==Xとすると、インデックス5を返します。
- 要素のインデックスを
フィボナッチ探索アルゴリズムの実装
#include <bits/stdc++.h>
using namespace std;
int fibonacciSearch(int A[], int x, int n) {
int fbM2 = 0;
int fbM1 = 1;
int fbM = fbM2 + fbM1;
int offset = -1;
while (fbM < n) {
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
while (fbM > 1) {
int i = min(offset + fbM2, n - 1);
if (A[i] < x) {
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM - fbM1;
offset = i;
} else if (A[i] > x) {
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
} else
return i;
}
if (fbM1 && A[offset + 1] == x) return offset + 1;
return -1;
}
int main() {
int n = 9;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 8;
int result = fibonacciSearch(arr, x, n);
if (result == -1) {
cout << "Element not found !!";
} else
cout << "Element found at index " << result;
return 0;
}
フィボナッチ探索アルゴリズムの計算複雑性
時間計算量
- 平均ケース
我々は、繰り返しのたびに探索空間を 1/3 / 2/3 に削減し、その結果、アルゴリズムは対数的な複雑さを持っています。フィボナッチ探索アルゴリズムの時間的複雑さは O(logn) です。
- 最良の場合
最良の時間的複雑さは O(1) です。これは比較対象の要素が最初の要素である場合に発生します。
- 最悪の場合
最悪の場合は、対象となる要素 X が常により大きな部分配列に存在する場合です。最悪の時間的複雑度は O(logn) です。これは平均ケースの時間複雑度と同じです。
空間計算量
このアルゴリズムは一時変数以外に余分な空間を必要としないので、空間の複雑さは O(1) です。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn