So sánh thời gian chạy

So sánh thời gian chạy của thuật toán Linear Search và thuật toán Binary Search
 avatar
user_1746670
c_cpp
a year ago
1.4 kB
11
Indexable
#include <bits/stdc++.h>
using namespace std;

int LinearSearch(int a[], int n, int x) {
    int i = 0;
	
    while (i < n && a[i] != x) {
        i++;
    }
    if (i < n) return i;
	
    return -1;
}

int BinarySearch_DQ(int a[], int left, int right, int x) {
    if (left > right) return -1;
	
    int mid = (left + right) / 2;
	
    if (x == a[mid])
        return mid;
    else if (x > a[mid])
        return BinarySearch_DQ(a, mid + 1, right, x);
    else
        return BinarySearch_DQ(a, left, mid - 1, x);
}

void PhatSinhMang(int a[], int n) {
    srand(0);
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 10000;
    }
}

void PhatSinhMangTang(int a[], int n) {
    srand(0);
	
    a[0] = rand() % 50;
	
    for (int i = 1; i < n; i++) {
        a[i] = a[i - 1] + rand() % 10;
    }
}

int main() {
    int ls1[1000];
    PhatSinhMang(ls1, 1000);
	
    int bs1[1000];
    PhatSinhMangTang(bs1, 1000);
	
    #if 0
    clock_t start, end;
    start = clock();
    LinearSearch(ls1, 1000, 300);
    end = clock();
    double t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Thoi gian tim kiem tuyen tinh la: " << t << " giay" << endl;
    #endif
	
    #if 1
    clock_t start, end;
    start = clock();
    BinarySearch_DQ(ls1, 0, 1000, 300);
    end = clock();
    double t = double(end - start) / CLOCKS_PER_SEC;
    cout << "Thoi gian tim kiem nhi phan la: " << t << endl;
    #endif
	
    return 0;
}
Editor is loading...
Leave a Comment