Data Structures & Algorithms: Big O Notation (Day 43) | FE Master

🎯 Big O: Thước đo độ "Ngáo" của code

Code chạy được là một chuyện. Code chạy nhanh hay chậm lại là chuyện khác. Làm sao biết code của bạn "xịn" hay "lởm"? Hãy dùng thước đo Big O.

1. Big O là cái quái gì?

Nó là cách các Dev chém gió về tốc độ tăng trưởng của thuật toán khi dữ liệu (N) tăng lên.

Hãy tưởng tượng bạn phải tìm một người tên "Nam" trong danh bạ.

2. Các cấp độ Big O (Từ Thần thánh đến Thảm họa)

🚀 O(1) - Constant (Hằng số) - Tốc độ ánh sáng

Ví dụ: "Nam ở số nhà 10". Bạn bay đến nhà số 10. Xong.

Dù khu phố có 10 nhà hay 1 tỷ nhà, bạn vẫn chỉ mất 1 giây để đến đúng địa chỉ. (Truy cập Array theo index, hoặc dùng HashMap).

int x = arr[100]; // 1 nhịp

✈️ O(log N) - Logarithmic - Tốc độ máy bay

Ví dụ: Tra từ điển hành động "Binary Search".

Mở giữa cuốn sách -> Không thấy -> Xé đôi vứt 1 nửa -> Tìm tiếp nửa còn lại.

Dữ liệu tăng gấp đôi, thời gian chỉ tăng thêm 1 tí xíu. (Cực xịn).

🚗 O(N) - Linear (Tuyến tính) - Tốc độ xe máy

Ví dụ: Tìm từng trang một từ đầu đến cuối.

Sách dày gấp đôi -> Tìm lâu gấp đôi. (Chấp nhận được).

🐢 O(N^2) - Quadratic (Bình phương) - Tốc độ rùa bò

Ví dụ: 2 vòng for lồng nhau (Nested Loop).

Dữ liệu tăng gấp đôi -> Thời gian tăng gấp 4. Dữ liệu tăng gấp 10 -> Thời gian tăng gấp 100.

Code kiểu này đi phỏng vấn là tạch ngay. (Bubble Sort).

3. Đánh đổi: Time vs Space

Đời không như mơ. Muốn nhanh (Time) thì tốn RAM (Space). Muốn tiết kiệm RAM thì chạy chậm.

Ví dụ: Muốn tìm đường nhanh nhất (Google Maps), máy chủ phải lưu hàng tỷ con đường (Tốn Space kinh khủng) để tính toán ra kết quả trong O(1) (Nhanh kinh khủng).

👉 Là kỹ sư, bạn phải biết chọn cái nào quan trọng hơn tùy tình huống.

🎯 Big O: Thước đo độ "Ngáo" của code

Code chạy được là một chuyện. Code chạy nhanh hay chậm lại là chuyện khác. Làm sao biết code của bạn "xịn" hay "lởm"? Hãy dùng thước đo Big O.

1. Big O là cái quái gì?

Nó là cách các Dev chém gió về tốc độ tăng trưởng của thuật toán khi dữ liệu (N) tăng lên.

Hãy tưởng tượng bạn phải tìm một người tên "Nam" trong danh bạ.

2. Các cấp độ Big O (Từ Thần thánh đến Thảm họa)

🚀 O(1) - Constant (Hằng số) - Tốc độ ánh sáng

Ví dụ: "Nam ở số nhà 10". Bạn bay đến nhà số 10. Xong.

Dù khu phố có 10 nhà hay 1 tỷ nhà, bạn vẫn chỉ mất 1 giây để đến đúng địa chỉ. (Truy cập Array theo index, hoặc dùng HashMap).

int x = arr[100]; // 1 nhịp

✈️ O(log N) - Logarithmic - Tốc độ máy bay

Ví dụ: Tra từ điển hành động "Binary Search".

Mở giữa cuốn sách -> Không thấy -> Xé đôi vứt 1 nửa -> Tìm tiếp nửa còn lại.

Dữ liệu tăng gấp đôi, thời gian chỉ tăng thêm 1 tí xíu. (Cực xịn).

🚗 O(N) - Linear (Tuyến tính) - Tốc độ xe máy

Ví dụ: Tìm từng trang một từ đầu đến cuối.

Sách dày gấp đôi -> Tìm lâu gấp đôi. (Chấp nhận được).

🐢 O(N^2) - Quadratic (Bình phương) - Tốc độ rùa bò

Ví dụ: 2 vòng for lồng nhau (Nested Loop).

Dữ liệu tăng gấp đôi -> Thời gian tăng gấp 4. Dữ liệu tăng gấp 10 -> Thời gian tăng gấp 100.

Code kiểu này đi phỏng vấn là tạch ngay. (Bubble Sort).

3. Đánh đổi: Time vs Space

Đời không như mơ. Muốn nhanh (Time) thì tốn RAM (Space). Muốn tiết kiệm RAM thì chạy chậm.

👉 Là kỹ sư, bạn phải biết chọn cái nào quan trọng hơn tùy tình huống.

CTDL & Giải thuật: Độ phức tạp Big O

lesson.content.title

🎯 Big O: Thước đo độ "Ngáo" của code

1. Big O là cái quái gì?

2. Các cấp độ Big O (Từ Thần thánh đến Thảm họa)

🚀 O(1) - Constant (Hằng số) - Tốc độ ánh sáng

✈️ O(log N) - Logarithmic - Tốc độ máy bay

🚗 O(N) - Linear (Tuyến tính) - Tốc độ xe máy

🐢 O(N^2) - Quadratic (Bình phương) - Tốc độ rùa bò

3. Đánh đổi: Time vs Space

CTDL & Giải thuật: Độ phức tạp Big O

lesson.content.title

🎯 Big O: Thước đo độ "Ngáo" của code

1. Big O là cái quái gì?

2. Các cấp độ Big O (Từ Thần thánh đến Thảm họa)

🚀 O(1) - Constant (Hằng số) - Tốc độ ánh sáng

✈️ O(log N) - Logarithmic - Tốc độ máy bay

🚗 O(N) - Linear (Tuyến tính) - Tốc độ xe máy

🐢 O(N^2) - Quadratic (Bình phương) - Tốc độ rùa bò

3. Đánh đổi: Time vs Space