Giải Luyện tập 1 Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán (trang 115) – SGK Tin học 11 Kết nối tri thức. Gợi ý: 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.
Câu hỏi/Đề bài:
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]:
A[j],A[j+1] = A[j+1]1,A[j]
Lời giả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)