Kompleksitas Algoritma Pencarian (Sequential Search) Menggunakan Rekursif

Sumber Gambar : GeeksforGeeks 

Menurut Wikipedia, Rekursi adalah proses pengulangan sesuatu dengan cara kesamaan-diri. Sebagai contohnya, saat dua cermin berada paralel antara satu dengan yang lain, gambar yang tertangkap adalah suatu bentuk rekursi tak-terbatas.

Menurut Qword, algoritma adalah urutan langkah-langkah logis penyelesaian sebuah masalah yang disusun secara logis dan sistematis.

Kompleksitas algoritma adalah seberapa efisien sebuah algoritma tersebut dihitung dari pemakaian waktu untuk proses dan ruang. Kompleksitas algoritma bisa dibedakan menjadi dua yaitu kompleksitas untuk algoritma rekursi dan bukan rekusi. Hal ini dikarenakan dalam penentuan untuk algoritma rekusi, terlebih dahulu harus ditentukan basis dan rekurensnya. Hal ini dapat dicontohkan pada algorima untuk mencari data pada sebuah larik atau array (pencarian beruntun).

(0)     Prosedur Pencarian Beruntun secara Iteratif (bukan Rekursif)

Procedure pencarianData (Input : A[0..n-1], k)

//Pencarian untuk sebuah nilai yang diberikan (k) untuk mencari dalam larik A[]

//Input : sebuah larik A[] dan sebuah kunci pencarian k

//Output : Index dari elemen pertama A[] yang sama dengan k atau bernilai -1 //jika tidak ada elemen yang sama.

 

i ← 0

while i < n and A[i] != k do

   i ← i + 1

if i < n return i

else return -1 

(1)         Prosedur Pencarian Beruntun secara Rekursif

SeqRec(n, A, k)

(a(1) Basis

Jika n = 0, kembalikan nilai -1.

(b(2)Rekurens

Jika n > 0,

-        Jika (A[n-1] == k), kembalikan nilai n-1

-        SeqRec((n-1), A, k)

(2)        Source Code Pencarian Beruntun Rekursif Bahasa C

int rek(int n, int A[], int k){

    if(n==0)

        return -1;

    else{

        if(A[n-1]==k) return n-1;

        rek(n-1, A, k);

    }

}

 

int main(){

    int i =0;

    int k =5;

    int n =4;

    int A[] = {1,2,3,4};

    printf("%d", rek(n, A,k));

}

 

(4)       Kompleksitas Waktu Algoritma Pencarian Beruntun Rekursif 

Bagian rekurens dipecahkan sebagai berikut

T(n)   = T(n-1) + 1                     substitusi  T(n-1) = T(n-2) + 1

= [T(n-2) + 1] + 1 = T(n-2) + 2  substitusi  T(n-2) = T(n-3) + 1

= [T(n-3) + 2] + 1 = T(n-3) + 3

= .....

       = T(0) + n

       = 0 + n

Jadi, T(n) = n  → T(n) ∈ O(n)

Subscribe to receive free email updates: