Độ phức tạp thuật toán (Big O Notation)

39%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

lesson.content.title

lesson.content.subtitle

🎯 Big O là gì? Tại sao Senior lương cao hơn Junior?

Vì Senior biết viết code chạy nhanh và tốn ít RAM. Big O là thước đo hiệu quả của thuật toán khi dữ liệu đầu vào (N) tăng lên vô tận.

1. Bảng xếp hạng Big O (Từ Thần thánh đến Rùa bò)

Big O	Tên	Tốc độ	Ví dụ điển hình
O(1)	Constant (Hằng số)	Thần tốc	Truy cập mảng a[i], Hash Table (Map). Dù N=1 tỷ thì vẫn mất 1ns.
O(log N)	Logarithmic (Logarit)	Siêu nhanh	Binary Search. Tìm trong 1 tỷ phần tử chỉ mất 30 bước.
O(N)	Linear (Tuyến tính)	Bình thường	Vòng lặp For duyệt từ đầu đến cuối mảng.
O(N log N)	Linearithmic	Khá nhanh	Merge Sort, Quick Sort, Heap Sort. Đây là chuẩn mực của việc sắp xếp.
O(N²)	Quadratic (Bình phương)	Chậm	2 vòng For lồng nhau (Bubble Sort). N=1000 thì máy chạy 1 triệu phép tính.
O(2^N)	Exponential (Mũ)	Rất chậm	Đệ quy Fibonacci ngây thơ. N=30 máy đã treo.
O(N!)	Factorial (Giai thừa)	Thảm họa	Bài toán người du lịch (TSP) thử mọi khả năng. N=20 là vũ trụ hủy diệt cũng chưa chạy xong.

2. Cách tính Big O nhanh (Mẹo thi FE)

Bỏ qua hằng số: O(2N) -> O(N). O(N + 1000) -> O(N).
Chỉ giữ lại số mũ cao nhất: O(N² + N + 1) -> O(N²).
Vòng lặp lồng nhau -> Nhân độ phức tạp.
Vòng lặp nối tiếp -> Cộng độ phức tạp (rồi lấy Max).

Ví dụ:


for (i = 0; i < N; i++) {       // O(N)
    for (j = 0; j < N; j++) {   // O(N)
        print(i, j);
    }
}
// -> Tổng: O(N * N) = O(N²)

for (k = 0; k < N; k++) {       // O(N)
    print(k);
}
// -> Toàn bộ chưởng trình: O(N² + N) -> Rút gọn: O(N²).

Quảng cáo • Advertisement

📢 Ad Space

Google AdSense

Day 38 Day 40

Trang chủ

PHASE 2: LOGIC & TỰ ĐỘNG HÓA (DAY 31 - 50)/Ngày 39/100

DAY 39🇯🇵 計算量 (Big O)

Độ phức tạp thuật toán (Big O Notation)

39%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

lesson.content.title

lesson.content.subtitle

🎯 Big O là gì? Tại sao Senior lương cao hơn Junior?

Vì Senior biết viết code chạy nhanh và tốn ít RAM. Big O là thước đo hiệu quả của thuật toán khi dữ liệu đầu vào (N) tăng lên vô tận.

1. Bảng xếp hạng Big O (Từ Thần thánh đến Rùa bò)

Big O	Tên	Tốc độ	Ví dụ điển hình
O(1)	Constant (Hằng số)	Thần tốc	Truy cập mảng a[i], Hash Table (Map). Dù N=1 tỷ thì vẫn mất 1ns.
O(log N)	Logarithmic (Logarit)	Siêu nhanh	Binary Search. Tìm trong 1 tỷ phần tử chỉ mất 30 bước.
O(N)	Linear (Tuyến tính)	Bình thường	Vòng lặp For duyệt từ đầu đến cuối mảng.
O(N log N)	Linearithmic	Khá nhanh	Merge Sort, Quick Sort, Heap Sort. Đây là chuẩn mực của việc sắp xếp.
O(N²)	Quadratic (Bình phương)	Chậm	2 vòng For lồng nhau (Bubble Sort). N=1000 thì máy chạy 1 triệu phép tính.
O(2^N)	Exponential (Mũ)	Rất chậm	Đệ quy Fibonacci ngây thơ. N=30 máy đã treo.
O(N!)	Factorial (Giai thừa)	Thảm họa	Bài toán người du lịch (TSP) thử mọi khả năng. N=20 là vũ trụ hủy diệt cũng chưa chạy xong.

2. Cách tính Big O nhanh (Mẹo thi FE)

Bỏ qua hằng số: O(2N) -> O(N). O(N + 1000) -> O(N).
Chỉ giữ lại số mũ cao nhất: O(N² + N + 1) -> O(N²).
Vòng lặp lồng nhau -> Nhân độ phức tạp.
Vòng lặp nối tiếp -> Cộng độ phức tạp (rồi lấy Max).

Ví dụ:


for (i = 0; i < N; i++) {       // O(N)
    for (j = 0; j < N; j++) {   // O(N)
        print(i, j);
    }
}
// -> Tổng: O(N * N) = O(N²)

for (k = 0; k < N; k++) {       // O(N)
    print(k);
}
// -> Toàn bộ chưởng trình: O(N² + N) -> Rút gọn: O(N²).

Quảng cáo • Advertisement

📢 Ad Space

Google AdSense

Day 38 Day 40