Question

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]

Answer 1

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²)

T = O(n) + O(n²) = O(n²)