Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
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 = T2(n) = \(2+n^2+1=n^2+3\) (đơn vị thời gian)
*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).
Các tiêu chí đánh giá tính hiệu quả của thuật toán hay chương trình giải một bài toán có thể khác nhau tùy vào mục đích và yêu cầu của dự án hoặc ứng dụng cụ thể. Dưới đây là một số thảo luận về các tiêu chí được đưa ra trong câu hỏi:
1. Tiêu chí thời gian chạy (runtime): Thời gian chạy của chương trình là một yếu tố quan trọng trong đánh giá tính hiệu quả của thuật toán hay chương trình. Nếu chương trình chạy nhanh, đáp ứng được yêu cầu về thời gian đối với ứng dụng cụ thể, thì đây là một tiêu chí quan trọng để đánh giá tính hiệu quả của chương trình.
2. Tiêu chí tiết kiệm bộ nhớ: Việc sử dụng bộ nhớ của chương trình cũng là một yếu tố quan trọng trong đánh giá tính hiệu quả của chương trình, đặc biệt là đối với các ứng dụng có yêu cầu về tài nguyên hạn chế. Nếu chương trình sử dụng ít bộ nhớ và đáp ứng được yêu cầu về tài nguyên, thì tiêu chí này cũng được coi là quan trọng.
3. Tiêu chí đơn giản, rõ ràng, dễ hiểu: Độ đơn giản, rõ ràng và dễ hiểu của chương trình cũng là một yếu tố quan trọng trong đánh giá tính hiệu quả của chương trình, đặc biệt là trong việc duy trì và phát triển sau này. Nếu chương trình được viết một cách đơn giản, rõ ràng và dễ hiểu, thì nó sẽ dễ dàng trong việc duy trì, nâng cấp, và áp dụng cho các tình huống khác nhau.
Câu lệnh in ra màn hình: print(".....")
Các bước thực hiện
- Phân tích bài toán.
- Độ phức tạp thuật toán.
a. Dựa trên mã lệnh thuật toán cho trong Hình 3.
b) Dựa trên mã lệnh thuật toán cho trong Hình 5.
1. Sắp xếp chèn (Insertion Sort)
Ý tưởng: Insertion Sort lấy ý tưởng từ việc chơi bài, dựa theo cách người chơi "chèn" thêm một quân bài mới vào bộ bài đã được sắp xếp trên tay.
2. Sắp xếp lựa chọn (Selection Sort)
Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị A' cần tìm.
3. Sắp xếp nổi bọt (Bubble Sort)
Ý tưởng: Bubble Sort, như cái tên của nó, là thuật toán đẩy phần tử lớn nhất xuống cuối dãy, đồng thời những phần tử có giá trị nhỏ hơn sẽ dịch chuyển dần về đầu dãy. Tựa như sự nổi bọt vậy, những phần tử nhẹ hơn sẽ nổi lên trên và ngược lại, những phần tử lớn hơn sẽ chìm xuống dưới.
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.