Câu 1 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n3 – n + 6.
b) T(n) = n5 + 7n2
logn + n! + 8n.
Câu 2 Em hãy viết hàm is_square_number(n) kiểm tra số tự nhiên n có là số chính phương
hay không.
Câu 3 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 3n4 – 2n + 5.
b) T(n) = n5 + 8n + 10nlogn + n!.
Câu 4
a) Em hãy nêu định nghĩa kí hiệu O-lớn.
b) Khi tính thời gian thực hiện chương trình, các phép toán nào được tính là 1 đơn vị thời gian?
Câu 5 Em hãy viết hàm xoá node đầu tiên của danh sách không rỗng L và hàm tìm kiếm phần
tử có khoá k trong danh sách L.
Câu 6 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n3 – 2n + 9.
b) T(n) = 4n5 + n2
logn + 7n + 10.
Câu 7 Ưu điểm của việc thiết kế thuật toán và chương trình theo mô đun là gì?

Question

Câu 1 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n3 – n + 6.
b) T(n) = n5 + 7n2
logn + n! + 8n.
Câu 2 Em hãy viết hàm is_square_number(n) kiểm tra số tự nhiên n có là số chính phương 
hay không.
Câu 3 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 3n4 – 2n + 5.
b) T(n) = n5 + 8n + 10nlogn + n!.
Câu 4
a) Em hãy nêu định nghĩa kí hiệu O-lớn.
b) Khi tính thời gian thực hiện chương trình, các phép toán nào được tính là 1 đơn vị thời gian?
Câu 5 Em hãy viết hàm xoá node đầu tiên của danh sách không rỗng L và hàm tìm kiếm phần 
tử có khoá k trong danh sách L.
Câu 6 Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n3 – 2n + 9.
b) T(n) = 4n5 + n2
logn + 7n + 10.
Câu 7 Ưu điểm của việc thiết kế thuật toán và chương trình theo mô đun là gì?

H_ậ_u · Accepted Answer

Phân tích độ phức tạp thời gian của các hàm thời gian

a) T(n) = 2n^3 - n + 6:

Phân tích từng hạng tử:
2n^3: Thuộc loại O(n^3), vì hệ số bậc cao nhất là 2 và bậc là 3.
-n: Thuộc loại O(n), vì hệ số là -1 và bậc là 1.
6: Thuộc loại O(1), vì đây là hằng số và không phụ thuộc vào n.
Xác định hạng tử chi phối:
Hạng tử có bậc cao nhất là 2n^3, do đó nó chi phối độ phức tạp của hàm.
Kết luận:
Độ phức tạp thời gian của hàm T(n) là O(n^3).

b) T(n) = n^5 + 7n^2 log(n) + n! + 8n:

Phân tích từng hạng tử:
n^5: Thuộc loại O(n^5), vì hệ số là 1 và bậc là 5.
7n^2 log(n): Thuộc loại O(n^2 log(n)), vì hệ số là 7 và bậc là 2 + 1 (log(n)).
n!: Thuộc loại O(n!), vì đây là giai thừa và có độ phức tạp tăng nhanh hơn bất kỳ hàm đa thức nào.
8n: Thuộc loại O(n), vì hệ số là 8 và bậc là 1.
Xác định hạng tử chi phối:
Hạng tử có độ phức tạp cao nhất là n!, do đó nó chi phối độ phức tạp của hàm.

Timi · Answer

Câu 1: 
a) T(n) = 2n3 – n + 6. Độ phức tạp của hàm này là O(n^3).
b) T(n) = n5 + 7n2 logn + n! + 8n. Độ phức tạp của hàm này là O(n!).

Câu 2: 
Để kiểm tra số tự nhiên n có phải là số chính phương hay không, bạn có thể sử dụng hàm is_square_number(n) như sau:
```csharp
bool is_square_number(int n)
{
    int sqr = (int)Math.Sqrt(n);
    return (sqr * sqr == n);
}
```

Câu 3: 
a) T(n) = 3n4 – 2n + 5. Độ phức tạp của hàm này là O(n^4).
b) T(n) = n5 + 8n + 10nlogn + n!. Độ phức tạp của hàm này là O(n!).

Câu 4: 
a) Kí hiệu O-lớn (Big O notation): Là ký hiệu được sử dụng để xác định giới hạn trên về độ phức tạp thời gian hoặc không gian bộ nhớ của một thuật toán.
b) Trong việc tính toán thời gian thực hiện chương trình, các phép toán cơ bản như cộng, trừ, nhân, chia được tính là một đơn vị thời gian.

Câu 5: 
Để viết hàm xoá node đầu tiên của danh sách không rỗng L và hàm tìm kiếm phần tử có khoá k trong danh sách L, bạn có thể sử dụng các thuật toán liên quan đến cấu trúc dữ liệu danh sách liên kết.

Câu 6: 
a) T(n) = n3 – 2n + 9. Độ phức tạp của hàm này là O(n^3).
b) T(n) = 4n5 + n2 logn + 7n + 10. Độ phức tạp của hàm này là O(n^5).

Câu 7: 
Ưu điểm của việc thiết kế thuật toán và chương trình theo mô-đun bao gồm tính tái sử dụng cao, quản lý mã nguồn dễ dàng, giảm thiểu lỗi logic và tăng tính bảo mật cho chương trình.

Câu 1 Tính độ phức tạp của các hàm thời gian sau: a) T(n) = 2n3 – n + 6. b) T(n) = n5 + 7n2 logn + n! + 8n. Câu 2 Em hãy viết hàm is_square_number(n) kiểm tra số tự nhiên n có là số chính phương...