Câu hỏi:
20/04/2023 292Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh trong thuật toán sắp xếp chọn là n(n-1)/2, với n là số phần tử trong mảng hoặc danh sách.
Số lần hoán đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần hoán đổi giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.
Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), hay n(n-1)/2 lần so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?
Câu 2:
Xác định độ phức tạp thời gian cho chương trình sau:
n = 1000
s = 0
for i in range (n);
s = s + i*(i+1)
print (s)
Câu 3:
Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?
Câu 4:
Xác định độ phức tạp thời gian tính toán cho chương trình sau:
n = 1000
sum = 0
i = 1
while i <n;
i = i*2
sum = sum + 1
print (sum)
Câu 5:
Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n(n - 2) + 4.
b) T(n) = n3 + 5n - 3.
Câu 6:
Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n3 + nlogn + 2n + 1.
b) T(n) = 3n4 + 2n2logn + 10.
về câu hỏi!