Phân tích các thuật toán | Phần 2 (Trường hợp xấu nhất, Trung bình và Tốt nhất)

 

Trong bài trước , chúng ta đã thảo luận về cách phân tích tiệm cận khắc phục các vấn đề của cách phân tích thuật toán ngây thơ. Trong bài đăng này, chúng tôi sẽ lấy một ví dụ về Tìm kiếm tuyến tính và phân tích nó bằng cách sử dụng phân tích Tiệm cận.
Chúng ta có thể có ba trường hợp để phân tích một thuật toán: 
1) Trường hợp xấu nhất 
2) Trường hợp trung bình 
3) Trường hợp tốt nhất
Chúng ta hãy xem xét việc triển khai Tìm kiếm tuyến tính sau đây. 
 

• C++

// C++ implementation of the approach #include <bits/stdc++.h> using namespace std;    // Linearly search x in arr[]. // If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) {     int i;     for (i = 0; i < n; i++) {         if (arr[i] == x)             return i;     }     return -1; }    // Driver Code int main() {     int arr[] = { 1, 10, 30, 15 };     int x = 30;     int n = sizeof(arr) / sizeof(arr[0]);     cout << x << " is present at index "          << search(arr, n, x);        getchar();     return 0; }    // This code is contributed // by Akanksha Rai

Đầu ra: 

30 có mặt ở chỉ số 2

Phân tích trường hợp xấu nhất (Thường được thực hiện) 
Trong phân tích trường hợp xấu nhất, chúng tôi tính toán giới hạn trên về thời gian chạy của một thuật toán. Chúng ta phải biết trường hợp gây ra số lượng tối đa các hoạt động được thực hiện. Đối với Tìm kiếm tuyến tính, trường hợp xấu nhất xảy ra khi phần tử cần tìm (x trong đoạn mã trên) không có trong mảng. Khi không có x, hàm search () sẽ so sánh nó với tất cả các phần tử của arr [] từng phần tử một. Do đó, độ phức tạp thời gian trong trường hợp xấu nhất của tìm kiếm tuyến tính sẽ là Θ (n).

Phân tích trường hợp trung bình (Đôi khi được thực hiện) 
Trong phân tích trường hợp trung bình, chúng tôi lấy tất cả các đầu vào có thể có và tính toán thời gian tính toán cho tất cả các đầu vào. Tính tổng tất cả các giá trị đã tính và chia tổng cho tổng số đầu vào. Chúng ta phải biết (hoặc dự đoán) phân phối các trường hợp. Đối với bài toán tìm kiếm tuyến tính, chúng ta hãy giả sử rằng tất cả các trường hợp đều được phân phối đồng đều (bao gồm cả trường hợp x không có mặt trong mảng). Vì vậy, chúng tôi tổng tất cả các trường hợp và chia tổng cho (n + 1). Sau đây là giá trị của độ phức tạp thời gian trung bình của trường hợp. 
 

Thời gian trường hợp trung bình =  
 
=
= Θ (n) 

Phân tích trường hợp tốt nhất (Bogus) 
Trong phân tích trường hợp tốt nhất, chúng tôi tính toán giới hạn dưới về thời gian chạy của một thuật toán. Chúng ta phải biết trường hợp gây ra số lượng tối thiểu các hoạt động được thực hiện. Trong bài toán tìm kiếm tuyến tính, trường hợp tốt nhất xảy ra khi x có mặt tại vị trí đầu tiên. Số lượng các phép toán trong trường hợp tốt nhất là không đổi (không phụ thuộc vào n). Vì vậy, độ phức tạp về thời gian trong trường hợp tốt nhất sẽ là Θ (1) 
Hầu hết, chúng tôi thực hiện phân tích trường hợp xấu nhất để phân tích các thuật toán. Trong phân tích tồi tệ nhất, chúng tôi đảm bảo giới hạn trên về thời gian chạy của một thuật toán là thông tin tốt. 
Phân tích trường hợp trung bình không dễ thực hiện trong hầu hết các trường hợp thực tế và nó hiếm khi được thực hiện. Trong phân tích trường hợp trung bình, chúng ta phải biết (hoặc dự đoán) phân phối toán học của tất cả các đầu vào có thể có. 
Phân tích trường hợp tốt nhất là không có thật. Đảm bảo giới hạn thấp hơn cho một thuật toán không cung cấp bất kỳ thông tin nào vì trong trường hợp xấu nhất, một thuật toán có thể mất nhiều năm để chạy.
Đối với một số thuật toán, tất cả các trường hợp tiệm cận đều giống nhau, tức là không có trường hợp xấu nhất và tốt nhất. Ví dụ, Merge Sort . Merge Sort thực hiện các phép toán Θ (nLogn) trong mọi trường hợp. Hầu hết các thuật toán sắp xếp khác đều có trường hợp xấu nhất và tốt nhất. Ví dụ: trong cách triển khai điển hình của Sắp xếp nhanh (trong đó trục được chọn làm phần tử góc), điều tồi tệ nhất xảy ra khi mảng đầu vào đã được sắp xếp và điều tốt nhất xảy ra khi các phần tử xoay luôn chia mảng thành hai nửa. Đối với sắp xếp chèn, trường hợp xấu nhất xảy ra khi mảng được sắp xếp ngược lại và trường hợp tốt nhất xảy ra khi mảng được sắp xếp theo cùng thứ tự với đầu ra.