1. Xác định độ phức tạp của thuật toán tìm kiếm tuần tự
🔻Chương trình tìm kiếm tuần tự được viết bằng mã lập trình Python và C++ như sau:
| Mã lập trình Python |
Mã lập trình C++ |
|
1. def LinearSearch(A, K):
2. for i in range(len(A)):
3. if A[i] == K:
4. return i
5. return -1
|
1. int LinearSearch(int A, int K, int N){
2. for(int i = 0; i < N; i++){
3. if (A[i] == K)
4. return i;}
5. return -1;}
|
📝Hướng dẫn thực hiện:
Bước 1. Phân tích thời gian tính toán của thuật toán.
- n là kích thước của mảng đầu vào.
- T(n)là thời gian thực hiện thuật toán.
Với mỗi bước lặp sẽ kiểm tra phần tử thứ i có bằng với phần tử cần tìm kiếm (dòng 3):
- Nếu bằng thì trả về chỉ số của phần tử tìm thấy và kết thúc (dòng 4) → có thể kết thúc khi chưa duyệt hết mảng (trường hợp đã tìm thấy phần tử)
- Trường hợp tồi nhất vòng lặp ở dòng 2 sẽ thực hiện n bước lặp, mỗi bước lặp sẽ thực hiện lệnh so sánh ở dòng 3 tốn 1 đơn vị thời gian.
Tìm thấy phần tử (thực hiện một lần ở dòng 4) hoặc không tìm thấy phần tử (thực hiện dòng 5) mất 1 đơn vị thời gian.
Tổng số phép tính cơ bản của chương trình trong trường hợp tồi nhất là T(n) = n+1.
Bước 2. Xác định độ phức tạp O-lớn của thuật toán
T(n) = n+1 = O(n+1) = O(max(n, 1)) = O(n)
Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.
@204215319938@@204215242432@
2. Xác định độ phức tạp của thuật toán sắp xếp chọn
🔻Chương trình sắp xếp chọn được viết bằng mã lập trình Python và C++ như sau:
| Mã lập trình Python |
Mã lập trình C++ |
|
1. def SelectionSort(A, n):
2. for i in range(n-1):
3. iMin = i
4. for j in range(i+1, n):
5. if A[j] < A[iMin]:
6. iMin = j
7. A[i], A[iMin] = A[iMin], A[i]
|
1. void SelectionSort(A){
2. for(int i = 0; i < N; i++){
3. int iMin = i;
4. for(int j = i+1; j < N; j++){
5. if (A[j] < A[iMin])
6. iMin = j;}
7. swap(A[i], A[iMin]);}
|
📝Hướng dẫn thực hiện:
Bước 1. Phân tích thời gian tính toán của thuật toán.
Gọi N là kích thước của mảng A, T(n) là thời gian chạy của thuật toán.
Vòng lặp tại dòng 2 biến i sẽ chạy từ 0 đến n−2, vậy vòng lặp này có n−1 bước lặp, với mỗi bước lặp chương trình sẽ thực hiện các lệnh sau:
- Lệnh gán tại dòng 3 tốn 1 đơn vị thời gian.
- Vòng lặp for tại dòng 4, biến j sẽ chạy từ i+1 đến n−1, nên vòng lặp này có n−i−1 bước lặp.
- Với mỗi bước lặp tại dòng 4 chương trình sẽ thực hiện, 1 lệnh so sánh tại dòng 5 tốn 1 đơn vị thời gian và một lệnh gán tại dòng 6 tốn 1 đơn vị thời gian (nếu điều kiện thoả mãn).
Tổng hợp lại ta thấy thời gian chạy chương trình trên là: T(n) = n2+3n-3
Bước 2. Xác định độ phức tạp O-lớn của thuật toán
Áp dụng quy tắc cộng ta có: T(n) = O(max(n2, 3n, −3)) = O(n2)
@204215389775@
