def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(0, n - i - 1):
if A[j] A[j + 1]:
# đổi chỗ

Question

def bubble_sort(A):
    n = len(A)
    for i in range(n):
        for j in range(0, n - i - 1):
            if A[j] > A[j + 1]:
                # đổi chỗ
                A[j], A[j + 1] = A[j + 1], A[j]
    xác định độ phức tạp  của thuật toán sắp xếp nổi bọt

huuhung1238 · Answer

Đáp án:
 
Giải thích các bước giải:
 Trường hợp xấu nhất (mảng đảo ngược hoàn toàn)
Phải so sánh và đổi chỗ nhiều nhấtO(n²)
 Trường hợp trung bình
O(n²)
 Trường hợp tốt nhất (mảng đã sắp xếp sẵn)
Với code hiện tại (không có tối ưu) vẫn chạy đủ vòngO(n²)
 Lưu ý quan trọng
Nếu thêm biến kiểm tra (flag) để dừng sớm:
 Khi đó:
Trường hợp tốt nhất: O(n)
 Độ phức tạp bộ nhớ
O(1) (sắp xếp tại chỗ, không dùng thêm bộ nhớ đáng kể)

def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(0, n - i - 1):
if A[j] > A[j + 1]:
# đổi chỗ
A[j], A[j + 1] = A[j + 1], A[j]
xác định độ phức tạp của thuật toán sắp xếp nổi bọt

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Group 2K9 Ôn Thi ĐGNL & ĐGTD Miễn Phí

Bạn muốn hỏi điều gì?

Tìm kiếm với hình ảnh

Hãy đăng nhập hoặc tạo tài khoản miễn phí!

Lưu vào

def bubble_sort(A): n = len(A) for i in range(n): for j in range(0, n - i - 1): if A[j] > A[j + 1]: # đổi chỗ A[j], A[j + 1] = A[j + 1], A[j] xác định độ phức tạp của thuật toán sắp xếp nổi bọt

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Group 2K9 Ôn Thi ĐGNL & ĐGTD Miễn Phí

Bạn muốn hỏi điều gì?

Lý do báo cáo vi phạm?

def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(0, n - i - 1):
if A[j] > A[j + 1]:
# đổi chỗ
A[j], A[j + 1] = A[j + 1], A[j]
xác định độ phức tạp của thuật toán sắp xếp nổi bọt