Bài 24 Đánh giá độ phức tạp thời gian thuật toán

Lớp 11Tin Học12 câu hỏiBài tập

Phần 1

Câu 1

(Câu 24.1 trang 75 SBT Tin học 11) Giả sử một chương trình P mô tả một thuật toán nào đó. Người ta đo được: T1 là thời gian nhập dữ liệu input và đưa vào bộ nhớ; T2 là thời gian chạy chương trình từ khi nhập xong dữ liệu input đến khi tính xong dữ liệu output; T3 là thời gian đưa dữ liệu output ra thiết bị ngoài chuẩn. Khi đó thời gian chạy chương trình

T (n)

dùng để tính độ phức tạp thời gian của thuật toán là phương án nào?

AT2.

BT1 + T2.

CT2 + T3.

DT1 + T2 + T3.

Câu 2

(Câu 24.2 trang 76 SBT Tin học 11) Cho chương trình: nhập n là số tự nhiên dương; gán S = 0; lặp với i từ 1 đến n, mỗi lần thực hiện S = S + i*i; sau đó in S. Thời gian chạy của chương trình được đánh giá là gì?

T (n) = n + 2

T (n) = 2 n + 1

T (n) = n^{2} + 2

T (n) = l o g_{2} n + 2

Câu 3

(Câu 24.3 trang 76 SBT Tin học 11) Cho chương trình: nhập n là số tự nhiên dương; gán i = 1, S = 0; trong khi i < n thì thực hiện S = S + i và i = i*2; sau đó in S. Thời gian chạy của chương trình được đánh giá là gì?

T (n) = 2 l o g_{2} n + 2

T (n) = n + 2

T (n) = n^{2} + 2

T (n) = 2 n^{2} - 3 n + 2

Câu 4

(Câu 24.4 trang 76 SBT Tin học 11) Cho chương trình tính tổng các phần tử của ma trận vuông A bậc n bằng hai vòng lặp lồng nhau: vòng lặp i chạy từ 0 đến n - 1, vòng lặp j chạy từ 0 đến n - 1, mỗi lần thực hiện S = S + A[i][j], sau đó in S. Thời gian chạy của chương trình được đánh giá là gì?

T (n) = n^{2} + 2

T (n) = n + 2

T (n) = 2 l o g_{2} n + 2

T (n) = 2 n^{2} - 2 n + 1

Câu 5

(Câu 24.8 trang 77 SBT Tin học 11) Với hàm

f (n) = n + 2 n l o g n + 10

, độ phức tạp theo kí hiệu O-lớn là gì?

O (n l o g n)

O (n)

O (l o g n)

O (1)

Câu 6

(Câu 24.8 trang 77 SBT Tin học 11) Với hàm

f (n) = 2 n^{2} + 3 n^{3} l o g n + n^{3 / 2}

, độ phức tạp theo kí hiệu O-lớn là gì?

O (n^{3} l o g n)

O (n^{2})

O (n^{3 / 2})

O (l o g n)

Câu 7

(Câu 24.8 trang 77 SBT Tin học 11) Với hàm

f (n) = 2^{n} + 3^{n} + 5^{n}

, độ phức tạp theo kí hiệu O-lớn là gì?

O (5^{n})

O (3^{n})

O (2^{n})

O (n^{5})

Phần 2

Câu 1

(Câu 24.5 trang 76 SBT Tin học 11) Cho chương trình tính theo đơn vị thời gian, A là một dãy số cho trước có n phần tử: hàm Tinh_tong_con_max(A), gán n = len(A), Tmax = A[0], sau đó dùng hai vòng lặp lồng nhau để tính S và cập nhật Tmax nếu S > Tmax.

a)Chương trình có hai vòng lặp lồng nhau nên thời gian chạy trong trường hợp xấu nhất có bậc hai theo n.

b)Thời gian chạy trong trường hợp xấu nhất được đánh giá là

T (n) = \frac{3}{2} n^{2} + \frac{5}{2} n + 1

c)Thành phần bậc cao nhất của

T (n)

là

\frac{3}{2} n^{2}

d)Độ phức tạp thời gian của chương trình là hằng số

O (1)

Câu 2

(Câu 24.6 trang 77 SBT Tin học 11) Đánh giá thời gian chạy của thuật toán sắp xếp chèn đã học trong sách giáo khoa.

a)Trong trường hợp xấu nhất, thuật toán sắp xếp chèn có thời gian chạy

T (n) = 2 n^{2} - 3 n + 2

b)Thành phần bậc cao nhất trong biểu thức thời gian chạy của thuật toán sắp xếp chèn là

2 n^{2}

c)Theo kí hiệu O-lớn, độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp chèn là

O (n^{2})

d)Trong trường hợp xấu nhất, sắp xếp chèn có độ phức tạp

O (l o g n)

Câu 3

(Câu 24.7 trang 77 SBT Tin học 11) Đánh giá thời gian chạy của thuật toán sắp xếp nổi bọt đã học trong sách giáo khoa.

a)Trong trường hợp xấu nhất, thuật toán sắp xếp nổi bọt có thời gian chạy

T (n) = 2 n^{2} - 2 n + 1

b)Thành phần bậc cao nhất trong biểu thức thời gian chạy của thuật toán sắp xếp nổi bọt là

2 n^{2}

c)Theo kí hiệu O-lớn, độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp nổi bọt là

O (n^{2})

d)Sắp xếp nổi bọt luôn có độ phức tạp

O (1)

vì chỉ đổi chỗ hai phần tử liền kề.

Câu 4

(Câu 24.9 trang 77 SBT Tin học 11) Xét các mệnh đề về kí hiệu O-lớn.

a)Có thể chứng minh

n = O (n^{2})

vì với n đủ lớn, n không lớn hơn một hằng số nhân với

n^{2}

b)Chẳng hạn với n > 1, ta có n <

n^{2}

, nên có thể chọn hằng số C = 1 để suy ra

n = O (n^{2})

c)Không thể có

n^{2} = O (n)

vì nếu

n^{2} < C n

với n đủ lớn thì suy ra n < C, điều này mâu thuẫn khi n tăng không giới hạn.

d)Vì

n = O (n^{2})

nên chắc chắn

n^{2} = O (n)

Câu 5

(Câu 24.10 trang 77 SBT Tin học 11) Chứng minh rằng nếu

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

và

g (n) = O (h (n))

thì

f (n) = O (h (n))

a)Từ

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

, tồn tại hằng số dương C₁ và n₁ sao cho

f (n) \leq C_{1} g (n)

với mọi n đủ lớn.

b)Từ

g (n) = O (h (n))

, tồn tại hằng số dương C₂ và n₂ sao cho

g (n) \leq C_{2} h (n)

với mọi n đủ lớn.

c)Với n đủ lớn, ta có

f (n) \leq C_{1} C_{2} h (n)

, nên

f (n) = O (h (n))

d)Từ

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

và

g (n) = O (h (n))

có thể kết luận

h (n) = O (f (n))

trong mọi trường hợp.

Tải Word | Làm thử | Giao đề bài này ngay