CTDL Độ phức tạp

Để đơn giản trong đánh giá, yếu tố thời gian khi xác định hiệu quả của thuật toán thường được đo bằng

• Đếm micro giây

• Đếm số các câu lệnh chính

• Đếm chính xác số câu lệnh rồi chia cho 2

• Đếm số kilobyte của thuật toán

Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản

• Tính khả thi (có thể thực hiện trong thời gian cho phép)

• Tính dừng (không được lặp vô hạn)

• Tính xác định (không được mập mờ)

• Tính phức tạp

Để viết chương trình chỉ để sử dụng một số ít lần và cái giá của thời gian viết chương trình chạy nhanh hoặc tiết kiệm nguồn tài nguyên vượt xa cái giá của chạy chương trình thì ta chọn thuật toán:

• Thuật toán đơn giản, dễ hiểu, dễ cài đặt

• Thuật toán sử dụng tiết kiệm nhất nguồn tài nguyên của máy tính,

• Thuật toán chạy nhanh nhất có thể được

• Thuật toán áp dụng được cho phạm vi rộng nhất có thể

Cho biết Qui tắc tổng để xác định độ phức tạp thuật toán Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà T1(n)= O(f(n)); T2(n)=O(g(n)) thì thời gian thực hiện đoạn P1 rồi P2 tiếp theo sẽ là

• T1(n) + T2(n) = O(max(f(n), g(n)))

• T1(n) + T2(n) = O( (f(n) hoặc g(n)))

• T1(n) + T2(n) = O(min(f(n), g(n)))

• T1(n) + T2(n) = O( (f(n)+ g(n)))

Xác định độ phức tạp tính toán Nếu tương ứng với P1 và P2 là T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là

• T1(n) *T2(n) = O(max(f(n), g(n)))

• T1(n) * T2(n) = O( (f(n) * g(n)))

• T1(n) * T2(n) = O( (f(n) + g(n)))

• T1(n) * T2(n) = O(min(f(n),g(n)))

Xác định độ phức tạp tính toán Nếu tương ứng với P1 và P2 là T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện P1 hoặc P2 sẽ là

• T1(n) *T2(n) = O(max(f(n), g(n)))

• T1(n) * T2(n) = O( (f(n) * g(n)))

• T1(n) * T2(n) = O( (f(n) + g(n)))

• T1(n) * T2(n) = O(min(f(n),g(n)))

Hai thành phần chính để đánh giá độ phức tạp của một thuật toán là

• Bộ xử lý và bộ nhớ

• Độ phức tạp và không gian

• Thời gian và không gian

• Dữ liệu và không gian

Trường hợp nào sau đây không tồn tại trong lý thuyết độ phức tạp

• Trường hợp tốt nhất

• Trường hợp xấu nhất

• Trường hợp trung bình

• Trường hợp rỗng

Chọn câu trả lời đúng nhất về thuật toán

• Thuật toán rất quan trọng với chương trình

• Thuật toán cần nhiều dữ liệu ra và vào

• Thuật toán là một dãy các bước hữu hạn, tất cả các phép toán phải đơn giản.

• Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác phép toán hoặc hành động để thực hiện vấn đề đặt ra.

Sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình. Chú ý: (logn) = Log cơ số 2 của n

• O(1), O(logn),O(n), O(nlogn)

• O(logn),O(n), O(nlogn), O(1)

• O(1), O(n), O(logn),O(nlogn)

• O(1), O(logn), O(nlogn), O(n)