1. Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

1 def BubbleSort(A):

2 n = len(A)

3 for i in range(n-1):

4 for j in range(n-1-i):

5 if A[j] > A[j+1]:

6 A[j],A[j+1] = A[j+1],A[j

2. Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O-lớn của chương trình.

1 def Mystery(n):

2 r = 0

3 for i in range(n-1):

4 for j in range(i+1,n):

5 for k in range(1,j):

6 r = r+1

7 return r

1. Giả sử rằng mỗi phép tính đơn được thực hiện trong 1 micro giây (1 μs = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ.

2. Hãy cho biết hàm sau thực hiện công việc gì. Xác định độ phức tạp thời gian của thuật toán.

1 def func(A):

2 n = len(A)

3 for i in range(n-1):

4 for j in range(i+1,n):

5 if A[i] > A[j]:

6 A[i],A[j] = A[j],A[i]