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 Searchuser_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