11_Lesson_độ phức tạp

1. Đánh giá thời gian thực hiện của chương trình

Đánh giá thời gian thực hiện của chương trình thực hiện bằng nhiều cách triển khai và chạy thuật toán, tuy nhiên cách tiếp cận này có một số vấn đề:

• Triển khai thuật toán không phù hợp với các chương trình phức tạp.

• Lãng phí thời gian triển khai nếu chương trình không được sử dụng.

• Thời gian chạy chương trình trên các thiết bị thông minh là khác nhau.

• Ngôn ngữ lập trình hoặc trình biên dịch có thể ảnh hưởng đến thời gian.

​Đánh giá độ phức tạp thời gian của thuật toán

1. Đánh giá thời gian thực hiện của chương trình

Giải pháp: Ước lượng thời gian chạy dựa trên việc tính tổng thời gian các phép tính đơn và các lệnh đơn của chương trình. 

Nhận định: Không chính xác hoàn toàn như thời gian thực nhưng có thể dùng để so sánh và ước lượng thời gian chạy chương trình khá chính xác.

Khung nguyên tắc đánh giá
Thời gian thực hiện của chương trình đang xét bằng:
1. Một đơn vị thời gian: phép so sánh, logic cơ bản, tính số học, lệnh đơn,...
2. Tổng đơn vị thời gian thực hiện mỗi lần lặp: vòng for, while.
3. Đơn vị thời gian lớn nhất của các lệnh rẽ nhánh: lệnh if nhiều nhánh rẽ.

​Đánh giá độ phức tạp thời gian của thuật toán

2. Phân tích độ phức tạp thời gian của thuật toán

Một bài toán có thể được giải bằng nhiều thuật toán, mỗi thuật toán sẽ có hàm thời gian T(n) khác nhau. Để lựa chọn thuật toán phù hợp nhất, ta phân tích bậc của hàm T(n) khi n tăng lên vô cùng thông qua O-lớn.

​Đánh giá độ phức tạp thời gian của thuật toán

2. Phân tích độ phức tạp thời gian của thuật toán

Bảng so sánh thời gian thực hiện của một số hàm chuẩn

​Đánh giá độ phức tạp thời gian của thuật toán

2. Phân tích độ phức tạp thời gian của thuật toán
Các quy tắc ước lượng thời gian thực hiện

a) Quy tắc chung

Khi tính đếm số phép toán cần thực hiện, các quy tắc ước lượng cho phép bỏ bớt những phần có bậc lớn thấp hơn, chỉ giữ lại những phần có bậc lớn cao nhất và các hằng số nhân C đều coi là 1.

b) Lời gọi hàm

Một lời gọi hàm được chia làm hai trường hợp:

• Lời gọi các hàm toán học sơ cấp, các hàm thư viện,... với đầu vào là giá trị cụ thể không phụ thuộc n → T(n)=O(1)

• Trường hợp còn lại sẽ được ước lượng độ phức tạp như với một thuật toán.

​Đánh giá độ phức tạp thời gian của thuật toán

2. Phân tích độ phức tạp thời gian của thuật toán

​Đánh giá độ phức tạp thời gian của thuật toán

Các quy tắc ước lượng thời gian thực hiện

c) Cấu trúc tuần tự và quy tắc lấy max

Cấu trúc tuần tự là một dãy gồm CC phép toán; CC là số xác định, không phụ thuộc nn.

• Nếu tất cả CC phép toán là sơ cấp →  T(n)=O(1)

• Thời gian thực hiện bằng ước lượng lớn nhất trong số các ước lượng của các phép toán có trong dãy.

d) Cấu trúc rẽ nhánh và quy tắc lấy max

Kiểm tra điều kiện là tính giá trị biểu thức logic gồm biểu thức số học và một phép so sánh →  T(n)=O(1)

Độ phức tạp thời gian của cấu trúc rẽ nhánh là độ phức tạp thời gian lớn nhất trong các độ phức tạp thời gian của các nhánh.
e) Cấu trúc vòng lặp và quy tắc nhân

Thời gian thực hiện cấu trúc vòng lặp được tính bằng số lần lặp nhân với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp.

​Đánh giá độ phức tạp thời gian của thuật toán

​Đánh giá độ phức tạp thời gian của thuật toán

​Đánh giá độ phức tạp thời gian của thuật toán

​Đánh giá độ phức tạp thời gian của thuật toán

Multiple Choice

Chương trình sau có hàm thời gian gần đúng là

• 
  

Multiple Choice

Thuật toán tìm kiếm nhị phân có độ phức tạp là

​Đánh giá độ phức tạp thời gian của thuật toán

​Xác định độ phức tạp của thuật toán tìm kiếm tuần tự
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)

Multiple Choice

Phương án nào sau đây là độ phức tạp thuật toán khi tìm kiếm được phần tử ngay lần đầu lặp?

• O(k).

• O(0).

• O(1).

• O(n).

Multiple Choice

Cho chương trình được viết như sau:

1. for i in range(0, n):

2. s = s + i

3. print(s)

Phương án nào sau đây nêu đúng độ phức tạp của chương trình trên?

• O(n²).

• O(1).

• O(n).

• O(s+n).

Multiple Choice

Phương án nào sau đây là cụm từ điền đúng vào vị trí trống trong đoạn văn sau: "Khi xác định độ phức tạp thời gian của một chương trình, cần dựa trên cơ sở ước lượng [ ] trong chương trình đó"?

• loại thiết bị sử dụng để chạy chương trình.

• tài nguyên máy tính cần sử dụng.

• xung nhịp của CPU trong một đơn vị thời gian.

• thời gian thực hiện của mỗi câu lệnh.

Multiple Choice

Phương án nào sau đây là hàm đo độ phức tạp thời gian của thuật toán?

• T(n)

• f(n)

• lamda(x)

• time(x)

Multiple Choice

Phương án nào sau đây nêu đúng hàm thời gian KHÔNG phụ thuộc vào nn?

• T(n)=10

• f(n)=n2+3

• T(n)=n

• f(n)=O(g(n))

Multiple Choice

Phương án nào sau đây nêu đúng độ phức tạp đối với phép toán là sơ cấp?

• O(n)

• O(1)

• O(C)

• O(2)

Multiple Choice

Phương pháp nào sau đây dùng để đánh giá độ phức tạp của chương trình?

• Đếm số câu lệnh trong chương trình.

• Tính toán độ phức tạp của thuật toán.

• Kiểm tra lượng dữ liệu đã tiêu hao.

• Chạy chương trình với các bộ dữ liệu.

Multiple Choice

Phương án nào sau đây nêu đúng độ phức tạp của chương trình?

Multiple Choice

Độ phức tạp nào sau đây dùng để đánh giá thuật toán?

• Độ phức tạp lưu trữ.

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

• Độ phức tạp thời gian.

• Độ phức tạp máy tính.

Multiple Choice

Kí hiệu trong hình bên là hàm chuẩn nào sau đây?

• Đa thức.

• Tuyến tính.

• Lũy thừa.

• Hằng số.

Multiple Choice

Kí hiệu nào sau đây là hàm thời gian tuyến tính?

• O(1).

• O(n)

Multiple Choice

Một thuật toán được coi là hiệu quả khi đạt được điều nào sau đây?

• Số lần thực hiện các câu lệnh là tối ưu.

• Thuật toán đơn giản, dễ cài đặt lên máy tính.

• Trả ra kết quả đúng với mọi dữ liệu vào.

• Lượng dữ liệu cần lưu trữ ở mức cao.

Multiple Choice

Phương án nào sau đây là độ phức tạp của hàm thời gian như hình

• O(2).

• O(n).

Multiple Choice

Hàm thời gian nào sau đây có độ phức tạp thời gian là bình phương?

Multiple Choice

Thời gian thực hiện thuật toán phụ thuộc vào yếu tố nào sau đây?

• Tốc độ xử lí dữ liệu của bộ xử lí trong máy.

• Loại máy tính được sử dụng để tính toán.

• Khối lượng dữ liệu trong quá trình tính toán.

• Số lượng câu lệnh có trong chương trình.

Multiple Choice

Ký hiệu O(n)O(n)O(n) trong phân tích độ phức tạp thời gian biểu thị điều gì?

• Chương trình có độ phức tạp tuyến tính

• Chương trình có độ phức tạp bình phương

• Chương trình có độ phức tạp mũ

• Chương trình có độ phức tạp hàng số

Multiple Choice

Quy tắc cộng trong tính độ phức tạp thời gian của thuật toán được áp dụng trong trường hợp nào?

• Khi có vòng lặp lồng nhau

• Khi thực hiện hai chương trình nối tiếp nhau

• Khi thực hiện phép toán nhân

• Khi thực hiện phép toán chia

Multiple Choice

Nếu chương trình có độ phức tạp thời gian T(n)=n2+3n+1T(n) = n^2 + 3n + 1T(n)=n2+3n+1, độ phức tạp thời gian của nó là gì?

• O(n2)O(n^2)O(n2)

• O(n)O(n)O(n)

• O(log⁡n)O(\log n)O(logn)

• O(n3)O(n^3)O(n3)

Multiple Choice

Trong trường hợp nào độ phức tạp thời gian của chương trình là O(1)O(1)O(1)?

• Khi chương trình có vòng lặp lồng nhau

• Khi chương trình có độ phức tạp tuyến tính

• Khi chương trình có độ phức tạp lũy thừa

• Khi chương trình chỉ có các phép toán đơn và không phụ thuộc vào nnn

Multiple Choice

Ký hiệu O(log⁡n)O(\log n)O(logn) được dùng khi độ phức tạp thời gian của thuật toán là gì?

• Tuyến tính

• Logarit

• Đa thức

• Mũ

Multiple Choice

Để tính độ phức tạp thời gian của chương trình với các phép toán lồng nhau, ta áp dụng quy tắc nào?

• Quy tắc cộng

• Quy tắc nhân

• Quy tắc chia

• Quy tắc cộng và chia

Multiple Choice

Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự LinearSearch(A, K) là:

• O(1)

• O(n)

• O(log n)

• O(n^2)

Multiple Choice

Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt BubbleSort(A) là:

• O(n)

• O(n^2)

• O(n log n)

• O(log n)

Multiple Choice

Độ phức tạp thời gian của BubbleSort trong trường hợp tốt nhất khi mảng đã sắp xếp là:

• O(n)

• O(n^2)

• O(n log n)

• O(1)