Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 is = 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 tim kiếm tuần tự,....

Vận dụng

Câu hỏi 1. 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ờ?

Bài Làm:

  • - 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) * (106us / phép tính)) = 3.6 * 106

    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 * (106us / 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) * (106us / 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) * (106us / phép tính)) = 3.6 * 106

Xem thêm Bài tập & Lời giải

Trong: Giải Tin học 11 định hướng KHMT Kết nối bài 25 Xác định độ phức tạp thời gian thuộc toán

Khởi động

Câu hỏi. 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 lời giải

Luyện tập

Câu hỏi 1. 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):

for A[j] > A[j#1]:

A[j],A{fj+1] = A[3+1]1,A[3]

Xem lời giải

Câu hỏi 2. 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.

Giải Tin học 11 định hướng KHMT Kết nối bài 25 Xác định độ phức tạp thời gian thuộc toán

Xem lời giải

Câu hỏi 2. 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.

Xem lời giải

Xem thêm các bài Giải tin học 11 định hướng Khoa học máy tính kết nối tri thức, hay khác:

Xem thêm các bài Giải tin học 11 định hướng Khoa học máy tính kết nối tri thức được biên soạn cho Học kì 1 & Học kì 2 theo mẫu chuẩn của Bộ Giáo dục theo sát chương trình Lớp 11 giúp bạn học tốt hơn.

Lớp 11 | Để học tốt Lớp 11 | Giải bài tập Lớp 11

Giải bài tập SGK, SBT, VBT và Trắc nghiệm các môn học Lớp 11, dưới đây là mục lục các bài giải bài tập sách giáo khoa và Đề thi chi tiết với câu hỏi bài tập, đề kiểm tra 15 phút, 45 phút (1 tiết), đề thi học kì 1 và 2 (đề kiểm tra học kì 1 và 2) các môn trong chương trình Lớp 11 giúp bạn học tốt hơn.

Giải sách giáo khoa lớp 11

Giải sách bài tập lớp 11

Trắc nghiệm lớp 11

Tài liệu tham khảo lớp 11

Giáo án lớp 11