Trang chủ Lớp 11 SGK Tin học 11 - Kết nối tri thức Chủ đề 6. Kĩ thuật lập trình Bài 24. Đánh giá độ phức tạp thời gian thuật toán trang 111 Tin học 11 Định hướng khoa học máy tính Kết nối tri thức: Quan sát và ước lượng thời gian thực hiện các đoạn chương ...

Bài 24. Đánh giá độ phức tạp thời gian thuật toán trang 111 Tin học 11 Định hướng khoa học máy tính Kết nối tri thức: Quan sát và ước lượng thời gian thực hiện các đoạn chương ...

Hướng dẫn trả lời bài 24. Đánh giá độ phức tạp thời gian thuật toán trang 111 SGK Tin học 11 Định hướng khoa học máy tính Kết nối tri thức. Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24. 2. Chương trình nào chạy nhanh hơn? Vì sao?...

Câu hỏi:

Khởi động

Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?

image

Hướng dẫn giải :

Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

Chương trình 1 chạy nhanh hơn, vì chương trình 1 có 1 vòng lặp, chương trình 2 có 2 vòng lặp.


Câu hỏi:

Câu hỏi mục I Hoạt động1

Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.

Hướng dẫn giải :

Vận dụng kiến thức mục 1 trang 111, 112 SGK để trả lời câu hỏi.

Lời giải chi tiết :

Chương trình 1: Thời gian thực hiện chương trình là T1=T1(n)=2+n+1=n+3 (đơn vị thời gian)

Chương trình 2: Thời gian thực hiện chương trình là T2=T1(n)=2+n2+1=n2+3 (đơn vị thời gian)


Câu hỏi:

Câu hỏi mục I - Câu số 1

Các lệnh và đoạn chương trình sau cần chạy trong bao nhiêu đơn vị thời gian?

image

Hướng dẫn giải :

Vận dụng kiến thức trong bài để trả lời câu hỏi.

Lời giải chi tiết :

a) T1=1+n//3=1+1000000//3 đơn vị thời gian

b) T2=1+1+(n//3)=2+1000000//3 đơn vị thời gian


Câu hỏi:

Câu hỏi mục I - Câu số 2

Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực” là đúng hay sai?

Hướng dẫn giải :

Vận dụng kiến thức mục 1 trang 111, 112 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

Sai. Trong một chương trình máy tính, có thể có nhiều phép toán tích cực (positive operations), cũng như các phép toán khác nhau, chẳng hạn phép toán cộng, trừ, nhân, chia, so sánh, gán giá trị, và các phép toán logic, v.v... Các phép toán tích cực là các phép toán thực hiện các tính chất tích cực của chương trình, như tính toán dữ liệu, xử lý logic, và đưa ra kết quả mong đợi.


Câu hỏi:

Câu hỏi mục II Hoạt động2

Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.

Hướng dẫn giải :

Vận dụng kiến thức mục 2 trang 113 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Một trong những yếu tố quan trọng để đánh giá hiệu suất của một thuật toán là độ phức tạp thời gian, tức là thời gian mà thuật toán mất để thực thi dựa trên kích thước đầu vào của vấn đề. Phân loại thuật toán dựa trên độ phức tạp thời gian là một phương pháp được sử dụng phổ biến để đánh giá và so sánh hiệu suất của các thuật toán khác nhau. Dưới đây là một số phân loại chính dựa trên độ phức tạp thời gian của thuật toán:

-O(1) (độ phức tạp thời gian hằng số): Đây là loại thuật toán có thời gian thực thi không thay đổi theo kích thước đầu vào. Thời gian thực thi của thuật toán này là cố định, vì vậy độ phức tạp thời gian là hằng số. Ví dụ: Truy cập vào phần tử trong mảng có kích thước cố định.

-O(log n) (độ phức tạp thời gian logarithmic): Đây là loại thuật toán có thời gian thực thi tăng theo logarit của kích thước đầu vào. Thuật toán này thường được sử dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.

-O(n) (độ phức tạp thời gian tuyến tính): Đây là loại thuật toán có thời gian thực thi tăng tỷ lệ trực tiếp với kích thước đầu vào. Ví dụ: Duyệt qua từng phần tử trong mảng một lần.

-O(n^2) (độ phức tạp thời gian bậc hai): Đây là loại thuật toán có thời gian thực thi tăng theo bình phương của kích thước đầu vào. Ví dụ: Thuật toán sắp xếp Bubble Sort, các thuật toán tìm kiếm không hiệu quả như Linear Search trong một mảng lồng nhau.

-O(n^k) (độ phức tạp thời gian bậc k): Đây là loại thuật toán có thời gian thực thi tăng theo lũy thừa của kích thước đầu


Câu hỏi:

Câu hỏi mục II Câu hỏi

Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = 2n(n - 2) + 4.

b) T(n) = n3 + 5n - 3.

Hướng dẫn giải :

Vận dụng kiến thức trong bài và kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

a) T(n) = 2n(n - 2) + 4 = 2n2 - 4n + 4 = O(n2)

b) T(n) = n3 + 5n – 3 = O(n3)


Câu hỏi:

Câu hỏi mục III Hoạt động3

Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.

Hướng dẫn giải :

Vận dụng kiến thức mục 3 trang 114 SGK để trả lời câu hỏi.

Lời giải chi tiết :

QT1. Quy tắc cộng: O(f(n)+g(n))=O(max(f(n),g(n)))

QT2. Quy tắc nhân:

- Với hằng số: O(C.f(n))=O(f(n))

- Với hàm số: O(f(n).g(n))=O(f(n)).O(g(n))


Câu hỏi:

Câu hỏi mục III Câu hỏi

Áp dụng các quy tắc trên để tính độ phức tạp của các hàm thời gian sau:

a) T(n) = n3 + nlogn + 2n + 1.

b) T(n) = 3n4 + 2n2logn + 10.

Hướng dẫn giải :

Vận dụng kiến thức mục 3 trang 114 SGK và kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

a)T(n) = O(n3)

a)T(n) = O(n4)


Câu hỏi:

Luyện tập 1

Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

   s = s + i*(i+1)

print (s)

Hướng dẫn giải :

Vận dụng kiến thức trong bài để trả lời câu hỏi.

Lời giải chi tiết :

Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.

Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.

Các phép toán trong vòng lặp:

Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).

Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)


Câu hỏi:

Luyện tập 2

Xác định độ phức tạp thời gian tính toán cho chương trình sau:

n = 1000

sum = 0

i = 1

while i <n;

  i = i*2

  sum = sum + 1

print (sum)

Hướng dẫn giải :

Vận dụng kiến thức trong bài và kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.

Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.

Các phép toán trong vòng lặp:

Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).

Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).

Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)


Câu hỏi:

Vận dụng 1

Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21.

Hướng dẫn giải :

Vận dụng kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh trong thuật toán sắp xếp chọn là n(n-1)/2, với n là số tử trong mảng hoặc danh sách.

Số lần hoán đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần hoán đổi giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.

Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), hay n(n-1)/2 lần so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.


Câu hỏi:

Vận dụng 2

Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.

Hướng dẫn giải :

Dựa vào kiến thức trong bài kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.

Lời giải chi tiết :

*Chương trình 1:

from collections import Counter

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.time()

for k in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.time()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# Sử dụng hàm Counter để đếm số lần lặp

counter = Counter(range(n))

# In số lần lặp

print("Số lần lặp: {}”.format(counter))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây”.format(elapsed_time))

*Chương trình 2:

import time

n = 1000

c = 0

# Ghi lại thời điểm bắt đầu

start_time = time.perf_counter()

for k in range(n):

 for j in range(n):

  c = c + 1

# Ghi lại thời điểm kết thúc

end_time = time.perf_counter()

# Tính thời gian hoàn thành

elapsed_time = end_time - start_time

# In số lần lặp

print("Số lần lặp: {}”.format(c))

# In thời gian thực thi

print("Thời gian thực thi của chương trình: {:.6f} giây”.format(elapsed_time))

Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:

Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).

Dụng cụ học tập

Học Tin học cần sách giáo khoa, máy tính, vở ghi chép, bút mực và phần mềm học tập liên quan.

Chia sẻ

Chia sẻ qua Facebook Chia sẻ

Sách Giáo Khoa: Kết nối tri thức với cuộc sống

- Bộ sách Kết nối tri thức với cuộc sống được biên soạn cho tất cả học sinh phổ thông trên mọi miền của đất nước, giúp các em hình thành và phát triển những phẩm chất và năng lực cần có đối với người công dân Việt Nam trong thế kỉ XXI. Với thông điệp “Kết nối tri thức với cuộc sống”, bộ SGK này được biên soạn theo mô hình hiện đại, chú trọng vai trò của kiến thức, nhưng kiến thức cần được “kết nối với cuộc sống”, bảo đảm: 1) phù hợp với người học; 2) cập nhật những thành tựu khoa học hiện đại, phù hợp nền tảng văn hóa và thực tiễn Việt Nam; 3) giúp người học vận dụng để giải quyết những vấn đề của đời sống: đời sống cá nhân và xã hội, đời sống tinh thần (đạo đức, giá trị nhân văn) và vật chất (kĩ năng, nghề nghiệp).

Đọc sách

Bạn có biết?

Tin học là môn khoa học nghiên cứu về quá trình tự động hóa thông tin bằng máy tính. Đây là nền tảng của kỷ nguyên số, mở ra những cơ hội mới trong mọi lĩnh vực từ y học đến truyền thông, và đóng vai trò quan trọng trong phát triển kinh tế và xã hội.

Nguồn : Wikipedia - Bách khoa toàn thư

Tâm sự Lớp 11

Lớp 11 - Năm học quan trọng, bắt đầu hướng đến những mục tiêu sau này. Hãy học tập chăm chỉ và tìm ra đam mê của mình để có những lựa chọn đúng đắn cho tương lai!'

- Học nhưng cũng chú ý sức khỏe nhé!. Chúc các bạn học tập tốt.

Nguồn : Sưu tập

Copyright © 2024 Giai BT SGK