BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN | Tin học 11 - Định hướng khoa học máy tính | Chủ đề 6: Kỹ thuật lập trình - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

Nội Dung Chính

  1. LUYỆN TẬP
  2. VẬN DỤNG

(Trang 115)

SAU BÀI HỌC NÀY EM SẼ:

  • Thực hành xác định độ phức tạp (O-lớn) của hàm thời gian.

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?

Nhiệm vụ 1

Xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự được thể hiện bằng chương trình sau:

hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-0

1 def LinearSearch (A,K):

2 for i in range(len(A)):

3 if A[i] == K:

4 return i

5 return -1

Hướng dẫn:

Bước 1. Phân tích thời gian tính toán của thuật toán.

Gọi n là kích thước của mảng đầu vào, T(n) là thời gian thực hiện thuật toán.

- Đối với mã lệnh trên, chương trình sẽ thực hiện duyệt mảng và với mỗi bước lặp sẽ kiểm tra phần từ thứ i có bằng với phần tử cần tìm kiếm không (dòng 3). Nếu bằng, thì chương trình sẽ trả về chỉ số của phần từ tìm thấy và kết thúc (dòng 4). Như vậy, chương trình có thể kết thúc khi chưa duyệt hết mảng (trường hợp đã tìm thấy phần tử) và tối đa là duyệt hết màng. Như vậy, trong trường hợp tồi nhất vòng lặp ở dòng 2 sẽ thực hiện n bước lặp, mỗi bước lặp sẽ thực hiện lệnh so sánh ở dòng 3 tốn 1 đơn vị thời gian.

- Lệnh trả về sẽ được thực hiện duy nhất 1 lần ở dòng 4 (trường hợp tìm thấy phần tử trong mảng) hoặc dòng 5 (trường hợp không tìm thấy phần tử trong mảng) mất 1 đơn vị thời gian.

Do đó, tổng số phép tính cơ bản của chương trình trong trường hợp tồi nhất là

T(n) = n+1.

Bước 2. Xác định độ phức tạp O-lớn của thuật toán

T(n) = n + 1 = O(n+1) = O(max(n, 1)) = O(n).

Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.

(Trang 116)

Nhiệm vụ 2

Xác định độ phức tạp của thuật toán sắp xếp chọn được thể hiện bằng chương trinh sau:

hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-1

1 def SelectionSort (A):

2 n = len(A)

3 for i in range(n-1):

4 iMin = i

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

6 if A[j] < A[iMin]:

7 iMin = j

8 A[i], A[iMin] A[iMin], A[i]

Hướng dẫn:

Ý tưởng của thuật toán sắp xếp chọn là tại mỗi bước thứ i của vòng lặp sẽ tìm chính xác phần tử tại vị trí thứ i, tức là sẽ tìm phần tử nhỏ nhất trong dãy từ A[i], A[i + 1],... A[n - 1] và đổi chỗ phần tử nhỏ nhất này với A[i].

Gọi n là kích thước của mảng A, T(n) là thời gian chạy của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

- Lệnh gán ở dòng 2 tốn 1 đơn vị thời gian.

- Vòng lặp tại dòng 3 biến i sẽ chạy từ 0 đến n - 2, vậy vòng lặp này có n - 1 bước lặp.

- Tại mỗi bước lập của lệnh for tại dòng 3 chương trình sẽ thực hiện các lệnh sau:

+ Lệnh gán tại dòng 4 tốn 1 đơn vị thời gian

+ Vòng lặp for tại lệnh 5, biến j sẽ chạy từ i + 1 đến n - 1, nên vòng lặp này có n-i-1 bước lặp. 

+ Với mỗi bước lặp tại dòng 5 chương chương trình trình sẽ sẽ thực thực hiện: hi

1 lệnh so sánh tại dòng 6 tốn 1 đơn vị thời gian và một lệnh gán tại dòng 7 tốn 1 1 đơn vị thời gian và một đơn vị thời gian (nếu điều kiện thoả mãn).

Như vậy mỗi bước lặp tại dòng 5 sẽ tốn tối đa 2 đơn vị thời gian.

+ 1 lệnh đồi chỗ tại dòng 8 tốn 3 đơn vị thời gian.

Tổng hợp lại ta thấy thời gian chạy chương trình trên là:

T(n)=1+hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-2(1+2(n-i-1)+3) 

T(n) = 1+4(n-1)+2hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-3(n-i-1) 

T(n)=1+4(n-1)+2hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-4k

T(n)=1+4(n-1)+n(n-1)

(Trang 117)

T(n) = n2 + 3n-3

Xác định độ phức tạp O-lớn của thuật toán:

T(n) = O(max(n², 3n, 3)) = O(n²)

Vậy thuật toán sắp xếp chọn có độ phức tạp thời gian bình phương.

LUYỆN TẬP

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

1 định nghĩa BubbleSort(A):

hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-5

1 def BubbleSort(A):

2 n = len(A)

3 for i in range(n-1):

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

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

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

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.

hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-6

1 def Mystery (n):

2 r = 0

3 for i in range(n-1):

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

5 for k in range(1,j):

6 r = r+1

7 return r

VẬN DỤNG

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

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.

hinh-anh-bai-25-thuc-hanh-xac-dinh-do-phuc-tap-thoi-gian-thuat-toan-13100-7

1 def func(A):

2 n = len(A)

3 for i in range(n-1):

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

5 if A[i] > A[j]:

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

Tin tức mới


Đánh giá

BÀI 25: THỰC HÀNH XÁC ĐỊNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN | Tin học 11 - Định hướng khoa học máy tính | Chủ đề 6: Kỹ thuật lập trình - Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

Tổng số sao của bài viết là: 5 trong 1 đánh giá
Xếp hạng: 5 / 5 sao

Bình Luận

Để Lại Bình Luận Của Bạn

Tin học 11 - Định hướng khoa học máy tính

  1. Chủ đề 1: Máy tính và xã hội tri thức
  2. Chủ đề 2: Tổ chức lưu trữ, tìm kiếm và trao đổi thông tin
  3. Chủ đề 3: Đạo đức, pháp luật và văn hóa trong môi trường số
  4. Chủ đề 4: Giới thiệu các hệ cơ sở dữ liệu
  5. Chủ đề 5: Hướng nghiệp với tin học
  6. Chủ đề 6: Kỹ thuật lập trình

Tin tức mới

Môn Học Lớp 11 - Kết Nối Tri Thức Với Cuộc Sống

Giải bài tập Toán 11 Tập 1

Âm Nhạc

Công Nghệ

Công Nghệ Công Nghệ Cơ Khí

GDTC_Cầu Lông

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

Giáo dục Thể Chất Bóng Chuyền

GDTC Bóng Đá

GDTC_Bóng Rổ

Hoạt động trải nghiệm hướng nghiệp

Lịch sử

Mỹ Thuật Điêu Khắc

Mỹ Thuật Đồ Hoạ_Tranh in

Mỹ Thuật Hội Hoạ

Mỹ Thuật Kiến Trúc

Mỹ Thuật Thiết Kế Công Nghiệp

Mỹ Thuật Thiết Kế Đa Phương Tiện

Mỹ Thuật Thiết Kế Đồ Hoạ

Mỹ Thuật Thiết Kế Sân Khấu Điện Ảnh

Mỹ Thuật Thiết Kế Thời Trang

Mỹ Thuật_Lý Luận Và Lịch Sử Mỹ Thuật

Ngữ Văn Tập 1

Ngữ Văn Tập 2

Sinh Học

Địa Lý

Tin Học

Toán tập 1

Toán tập 2

Vật lý

Tin học 11 - Định hướng khoa học máy tính

Giải bài tập Toán 11 Tập 2

Giải bài tập Vật lý 11

Giải bài tập Sinh học 11

Giải bài tập Hóa học 11

Bộ Sách Lớp 11

Giáo Dục Việt Nam

Bộ Sách Giáo Khoa của Nhà Xuất Bản Giáo Dục Việt Nam

Tài liệu học tập

Đây là tài liệu tham khảo hỗ trợ trong quá trình học tập

Global Success & Bộ Giáo Dục - Đào Tạo

Bộ sách Global Success & Bộ Giáo Dục - Đào Tạo là sự kết hợp giữa ngôn ngữ Tiếng Anh theo lối giảng dạy truyền thống và cập nhật những phương thức quốc tế

Cánh Diều

Bộ sách giáo khoa của Nhà xuất bản Cánh Diều

Kết Nối Tri Thức Với Cuộc Sống

Sách giáo khoa của nhà xuất bản Kết Nối Tri Thức Với Cuộc Sống

Sách Kết Nối Tri Thức Với Cuộc Sống

Lớp 1

Sách giáo khoa dành cho lớp 1

Lớp 6

Sách giáo khoa dành cho lớp 6

Lớp 5

Sách giáo khoa dành cho lớp 5

Lớp 4

Sách giáo khoa dành cho lớp 4

Lớp 2

Sách giáo khoa dành cho lớp 2

Lớp 3

Sách giáo khoa dành cho lớp 3

Lớp 7

Sách giáo khoa dành cho lớp 7

Lớp 8

Sách giáo khoa dành cho lớp 8

Lớp 9

Sách giáo khoa dành cho lớp 9

Lớp 10

Sách giáo khoa dành cho lớp 10

Lớp 11

Sách giáo khoa dành cho lớp 11

Lớp 12

Sách giáo khoa dành cho lớp 12

Liên Kết Chia Sẻ

** Đây là liên kết chia sẻ bới cộng đồng người dùng, chúng tôi không chịu trách nhiệm gì về nội dung của các thông tin này. Nếu có liên kết nào không phù hợp xin hãy báo cho admin.