0.24

0.94

32

Vòng lặp 1: Chọn phần tử nhỏ nhất là 1 (ở vị trí 0). Vì 1 đã ở vị trí đầu tiên, không cần hoán đổi gì → [1, 9, 2, 3, 4, 7, 6, 2]

Vòng lặp 2: Chọn phần tử nhỏ nhất là 2 (ở vị trí 2). Hoán đổi 9 và 2 → [1, 2, 9, 3, 4, 7, 6, 2]

Vòng lặp 3: Chọn phần tử nhỏ nhất là 2 (ở vị trí 7). Hoán đổi 9 và 2 → [1, 2, 2, 3, 4, 7, 6, 9]

Vòng lặp 4: Chọn phần tử nhỏ nhất là 3 (ở vị trí 3). Vì 3 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 7, 6, 9]

Vòng lặp 5: Chọn phần tử nhỏ nhất là 4 (ở vị trí 4). Vì 4 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 7, 6, 9]

Vòng lặp 6: Chọn phần tử nhỏ nhất trong mảng [7, 6, 9] là 6 (ở vị trí 5). Hoán đổi 7 và 6 → [1, 2, 2, 3, 4, 6, 7, 9]

Vòng lặp 7: Chọn phần tử nhỏ nhất trong mảng [7, 9] là 7 (ở vị trí 6). Vì 7 đã ở vị trí đầu tiên của phần chưa được sắp xếp, không cần hoán đổi gì → [1, 2, 2, 3, 4, 6, 7, 9]

Dưới đây là đoạn mã mẫu:

def f(A, B, n):

    total = 0

    for i in range(n):

        At = max(0, A[0][i] - A[1][i])

        Bt = max(0, B[0][i] - B[1][i])

        total += At + Bt

    return total

n = 5

A = [[20, 20, 10, 21, 18],[20, 15, 11, 13, 13]]

B = [[23, 0, 17, 22, 12],[20, 14, 11, 13, 9]]

total = f(A, B, n)

print(total)

TH1. N là số lẻ → Hiển thị luôn kết quả là 0 → T(n) = 3 → O(1).

TH2. N là số chẵn → Thực hiện vòng lặp bên trong khối lệnh IF → Vòng lặp chạy từ 0 đến N+1: \(\sum_{i = 0}^{n} i\)→T(n) = n + 3 → O(n).