Giải SGK Tin học 11 KNTT Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán có đáp án

29 người thi tuần này 4.6 709 lượt thi 5 câu hỏi

Câu 1/5

Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?

Xem đáp án

Lời giải

Đánh giá được mức đơn giản của thuật toán, từ đó tìm ra được cách giải nhanh nhất

Câu 2/5

Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

def BubbleSort(A):

n = len(A)

for i in range(n-1):

   for j in range(n-1-i):

          if A[j] > A[j+1]:

                   A[j],A[j+1] = A[j+1]1,A[j]

Xem đáp án

Lời giải

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²)

T=O(n)+O(n²)=O(n²)Top of Form

Câu 3/5

Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.

def Mystery(n):

      r=0

      for i in range(n-1):

            for j in range(i+1,n):

                    for k in range(1,j):

                         r=r+1

    return r

Xem đáp án

Lời giải

Hàm "Mystery(n)" sẽ trả về giá trị là r.

Độ phức tạp thời gian của chương trình này là O(n³)

Câu 4/5

Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 us = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ?

Xem đáp án

Lời giải

1.Thuật toán tìm kiếm tuần tự:

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

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (10⁶ us / phép tính) = 10⁶

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * (60 giây / phút) * (10⁶us / phép tính) = 6 * 10⁷

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính) = 3.6 * 10⁹

2.Thuật toán sắp xếp chèn:

- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(10²

- Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * (10⁶us / phép tính)) =10³

- Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 6 * 10⁴

- Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶

3. Thuật toán sắp xếp chọn:

- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)

- Giá trị lớn nhất của n là: n = sqrt(1 giây * (10⁶us / phép tính)) = 1000.

Thời gian thực thi là 1 phút:

Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 60000.

Thời gian thực thi là 1 giờ:

Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶Bottom of Form

Câu 5/5

Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.

def func(A):

       n=len(A)

       for i in range(n-1):

             for j in range(i+1,n):

                            if A[j] > A[j]:

                                          A[j],A[j] = A[j],A[i]

Xem đáp án

Lời giải

Công việc của hàm là thực hiện sắp xếp.

Độ phức tạp của thuật toán là O(n2)

Lớp 12

Lớp 11

Lớp 10

Ôn vào 10

Lớp 9

Lớp 8

Lớp 7

Lớp 6

Ôn vào 6

Lớp 5

Lớp 4

Lớp 3

Lớp 2

Lớp 1

Đại học

ĐGNL - ĐGTD

Tốt nghiệp THPT

Ôn vào 10

Ôn vào 6

V-ACT

HSA

TSA

SPT

Toán

Văn

Tiếng Anh

Vật lý

Hóa học

Sinh học

Lịch sử

Địa lý

Giáo dục Kinh tế và Pháp luật

Tin học

Công nghệ

Toán

Văn

Tiếng Anh

Vật lí

Hóa học

Sinh học

Lịch sử

Địa lí

Giáo dục Kinh tế và Pháp luật

Tin học

Công nghệ

Toán

Văn

Tiếng Anh

Vật lí

Hóa học

Sinh học

Lịch sử

Địa lí

Giáo dục Kinh tế và Pháp luật

Tin học

Công nghệ

Toán

Văn

Tiếng Anh

Vật lý

Hóa học

Sinh học

Lịch sử

Địa lí

Giáo dục Kinh tế và Pháp luật

Tin học

Công nghệ

Toán

Văn

Tiếng Anh

Vật lý

Hóa học

Sinh học

Khoa học tự nhiên

Tin học

Lịch sử

Địa lí

Toán

Văn

Tiếng Anh

Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

def BubbleSort(A):

n = len(A)

for i in range(n-1):

for j in range(n-1-i):

if A[j] > A[j+1]:

A[j],A[j+1] = A[j+1]1,A[j]

Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.

def Mystery(n):

r=0

for i in range(n-1):

for j in range(i+1,n):

for k in range(1,j):

r=r+1

return r

Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.

def func(A):

n=len(A)

for i in range(n-1):

for j in range(i+1,n):

if A[j] > A[j]:

A[j],A[j] = A[j],A[i]