Độ phức tạp của thuật toán (CTDL-GT) - Bài 1

Như thế nào là thuật toán hiệu quả : 

+ Tốc độ thực thi
+ Tính chính xác
+ Đơn giản , dễ hiểu , dễ bảo trì
+ Mức phổ dụng
+ Chi phí sử dụng tài nguyên : Bộ nhở , thời gian sử dụng CPU.



Phương pháp đánh giá độ phức tạp của giải thuật :

+ Dựa vào thời gian mà Thuật toán chạy đến khi ra kết quả.
+  Dựa vào phép toán thực hiện : phép so sánh, phép gán.



Nguyên tắc tính độ phức tạp của thuật toán : 

+ n : Kích thước đầu vào của dữ liệu
Ví dụ như truyền vào mảng có 1000 phần tử => chính là kích thước đầu vào của phần tử

+ Mô tả độ phức tạp của thuật toán qua hàm O(n)

+ Các nguyên tắc đánh giá : 

Nguyên tắc cộng và Nguyên tắc nhân : 

*Nguyên tắc cộng :  Trong chương trình P có 2 phần O1 và O2 (tức là nó nối tiếp nhau thực hiện O1 rồi mới đến O2)
=> Độ phức tạp được dựa vào độ phức tạp của phần có độ phức tạp lớn nhất
VD : P1 thức hiện mất 3s , P2 thực hiện mất 4s => độ phức tạp của chương trình =4s

*Nguyên tắc nhân : Trong chương trình P có 2 khối code lồng nhau
VD : 2 vòng for lồng nhau chẳng hạn
=> Độ phức tạp được tính bằng cách lấy độ phức tạp của 2 vòng for này rồi nhân với nhau


Bảng sắp xếp độ phức tạp của thuật toán theo thứ tự tăng dần từ trên xuống dưới :

4.Làm thế nào để đánh giá mức độ tối ưu của thuật toán.

- Ví dụ : 
Tìm phần tử x trong mảng n phần tử :

- Ở ví dụ trên : 

 + Ta dùng số phép so sánh dùng là thước đo.
  
  + Ở mỗi bước của vòng lặp trên ta thực hiện 2 phép so sánh.

+ Ở cuối vòng lặp thực hiện 1 phép so sánh.

+ Như vậy nếu trong trường hợp x có mặt trong vòng lặp ta phải thực hiện
2i+1 lần.

+ Trong trường hợp xấu nhất thì tổng số lần so sánh là 2n+2 lần.

+ Từ đó thuật toán tìm kiếm tuần tự này đòi hỏi tối đa O(n) phép so sánh
ví xét 2n+2 (ta bỏ qua hằng số )