피보나치 검색

1. 피보나치 검색 알고리즘
2. 피보나치 검색 예
3. 피보나치 검색 알고리즘 구현
4. 피보나치 검색 알고리즘 복잡성

피보나치 검색은 효율적인 간격 검색 알고리즘입니다. 분할 및 정복 전략을 기반으로하며 배열도 필요하다는 점에서 이진 검색과 유사합니다. 정렬됩니다. 더욱이 두 알고리즘의 시간 복잡도는 로그입니다. 피보나치 수열을 활용하기 때문에 피보나치 검색이라고합니다. (현재 숫자는 두 전임자의 합계F[i] = F[i-1] + F[i-2],F[0]= 0&F[1]=1은 연속 된 처음 두 숫자입니다.) 배열을 피보나치 숫자로 주어진 크기로 두 부분으로 나눕니다. 이진 검색에 필요한 나누기, 곱하기 및 비트 시프트에 비해 더하기 및 빼기 연산 만 사용하는 계산 친화적 인 방법입니다.

피보나치 검색 알고리즘

n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고,X요소를 찾으려고합니다.

피보나치 검색 예

배열이 있다고 가정합니다: (1, 2, 3, 4, 5, 6, 7). X= 6 요소를 찾아야합니다.

배열에는 7 개의 요소가 있습니다. 따라서n= 7.n보다 큰 가장 작은 피보나치 수는 8입니다.

피보나치 검색 알고리즘 구현

#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)입니다.