Dựa vào hướng dẫn của Nhiệm vụ 2 trang 116 SGK kết hợp kiến thức thực tế của bản thân Lời giải Câu hỏi 2 trang 84 Tin học 11 - Kết nối tri thức, Luyện tập 1 - trang 115 Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán SGK Tin học 11 - Kết nối tri thức.
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):
if A[j] > A[j+1]:
Advertisements (Quảng cáo)
A[j],A[j+1] = A[j+1]1,A[j]
Dựa vào hướng dẫn của Nhiệm vụ 2 trang 116 SGK kết hợp kiến thức thực tế của bản thân để trả lời câu hỏi.
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2)
T=O(n)+O(n2)=O(n2)