Câu hỏi:

27/11/2023 135

Viết chương trình tạo dãy A có n phần tử với giá trị ngẫu nhiên. Sau đó tính thời gian chạy của lệnh sắp xếp A.sort() của Python và so sánh thời gian này với các thời gian chạy của các thuật toán em đã biết (xem Câu 23.8). Em có nhận xét gì về kết quả thu được?

Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).

Tổng ôn toán Tổng ôn sử Các môn khác

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Thời gian chạy sắp xếp theo phương thức sort() nhanh hơn hẳn ba thuật toán sắp xếp đã biết.

Ví dụ với n = 10000, kết quả tính toán có thể như sau (tính theo giây).

1 Sắp xếp chèn: 10.774742800943896

2 Sắp xếp chọn: 10.29863730903126

3 Sắp xếp nổi bọt: 20.886252708118348

4 Sắp xếp Python: 0.0012119000311948998

Thời gian chạy sắp xếp theo phương thức sort() nhanh hơn hẳn ba thuật toán sắp xếp đã biết.

Ví dụ với n = 10000, kết quả tính toán có thể như sau (tính theo giây).

1 Sắp xếp chèn: 10.774742800943896

2 Sắp xếp chọn: 10.29863730903126

3 Sắp xếp nổi bọt: 20.886252708118348

4 Sắp xếp Python: 0.0012119000311948998

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Để chứng minh một thuật toán là đúng cần phải làm gì? Chọn phương án đúng nhất trong các phương án sau:

A. Cần tiến hành kiểm thử chương trình cài đặt thuật toán, kiểm thử càng nhiều càng tốt.

B. Cần cài đặt thuật toán trên càng nhiều ngôn ngữ lập trình càng tốt.

C. Cần chạy thử chương trình cài đặt thuật toán xem thời gian chạy có nhanh hay không.

D. Cần chứng minh bằng toán học chặt chẽ tính đúng của thuật toán.

Xem đáp án » 13/07/2024 796

Câu 2:

Giả sử một chương trình đã được kiểm tra chạy chính xác với hơn 1000 lần test. Mệnh đề nào sau đây là đúng?

A. Chương trình đó hoàn toàn chính xác. 

B. Chương trình đó chắc là sai ít đúng nhiều. 

C. Chương trình đó có độ tin cậy cao.

D. Chưa thể nói gì được về chương trình đó.

Xem đáp án » 13/07/2024 782

Câu 3:

Viết chương trình thực hiện các việc sau:

– Nhập dãy số A từ bàn phím.

– Thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A.

– Tính thời gian chạy của từng thuật toán trên đối với dãy

A, kết quả đưa ra màn hình.

Xem đáp án » 27/11/2023 619

Câu 4:

Hàm sau tạo một dãy số nguyên có n phần tử và các giá trị nằm ngẫu nhiên trong phạm vi [a, b].

1 def sinh_day(n,a,b):

2 from random import randint

3 A = [randint(a, b) for i in range(n)] 

4 return A

Em hãy viết chương trình tạo dãy A như trên với độ dài n và thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A. Sau đó tính thời gian chạy của các thuật toán này. Ghi lại bảng kết quả với các giá trị của n = 100, 1000, 10 000, 100 000.

Xem đáp án » 13/07/2024 402

Câu 5:

Trong các bài toán sau, kích thước đầu vào của bài toán là gì, được tính như thế nào?

a) Bài toán sắp xếp dãy số A theo thứ tự tăng dần.

b) Bài toán tính tổng 1+ 2 + ... + n với n là số tự nhiên cho trước.

c) Bài toán tính gcd(a,b) – ước chung lớn nhất của hai số tự nhiên cho trước a, b.

Xem đáp án » 27/11/2023 350

Câu 6:

Với thuật toán sắp xếp chèn (trong sách giáo khoa), cùng kích thước n, thì bộ dữ liệu kiểm thử nào cho thời gian chạy:

a) Nhanh nhất?

b) Chậm nhất?

Xem đáp án » 13/07/2024 348

Câu 7:

Mệnh đề sau có đúng không?

Muốn chứng minh một chương trình chạy đúng chỉ cần thực hiện thật nhiều việc kiểm thử (test). Nếu kiểm tra trên tất cả các bộ dữ liệu kiểm thử đều đúng thì chương trình đúng.

Xem đáp án » 13/07/2024 179

Bình luận


Bình luận
Đăng ký gói thi VIP

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Siêu tiết kiệm - Được thi tất cả các đề của các lớp có trên Khoahoc.vietjack.com
  • Ngân hàng câu hỏi trắc nghiệm theo các mức độ Nhận biết, Thông hiểu, Vận dụng, Vận dụng cao.
  • Luyện chuyên sâu, rèn tốc độ với trọn bộ đề thi thử, đề minh họa, chính thức các năm.
  • Hỏi bài tập với đội ngũ chuyên môn cao của chúng tôi.

Đặt mua

Vietjack official store