Review Phase 2 Part 1: Algorithms Master

40%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

Chúc mừng bạn! Đây là phần khó nuốt nhất đối với dân ngoại đạo IT. Nếu bạn hiểu được 70% nội dung vừa rồi, bạn đã có tư duy của một Lập trình viên.

Hãy tự hỏi mình những câu sau, nếu chưa trả lời được, hãy quay lại bài cũ:

□ Trace Table: Có tự kẻ bảng và chạy tay được một vòng lặp For 3 lớp lồng nhau không?
□ Sorting: Phân biệt được cách Bubble Sort và Selection Sort tráo đổi phần tử khác nhau thế nào? Quick Sort chọn Pivot ra sao?
□ Searching: Khi nào ĐƯỢC PHÉP dùng Binary Search? (Đáp án: Khi mảng đã sort).
□ Stack/Queue: DFS dùng cái gì? BFS dùng cái gì?
□ Linked List: Tại sao chèn vào giữa thì nhanh hơn Array?
□ Big O: Nhìn code đoán được độ phức tạp ngay lập tức.

Cho thuật toán sau:


Function Magic(A, n)
    If n <= 1 return A
    Left = Magic(A[0..n/2], n/2)
    Right = Magic(A[n/2..n], n - n/2)
    Return Merge(Left, Right)

Hỏi: Đây là thuật toán gì và độ phức tạp bao nhiêu?

👉 Xem đáp án

Đáp án: Đây là Merge Sort.

Độ phức tạp: O(N log N).

Chúng ta sẽ tạm biệt các con số trừu tượng để đến với thế giới Code thực tế.

Cách tổ chức bộ nhớ (Stack/Heap), Lập trình hướng đối tượng (Class/Object) và các Design Pattern sẽ là hành trang tiếp theo.

Thuật toán	Độ phức tạp (TB)	Khi nào dùng?	Lưu ý
Bubble/Selection Sort	O(N²)	Học cho biết, hoặc N < 100.	Rất chậm.
Quick Sort	O(N log N)	Mặc định khi cần sort.	Nhanh nhất thực tế. Unstable.
Merge Sort	O(N log N)	Cần Stable Sort.	Tốn RAM.
Linear Search	O(N)	Mảng lộn xộn, chưa sort.	Chậm.
Binary Search	O(log N)	Mảng ĐÃ SORT.	Siêu nhanh.
Hash Table	O(1)	Cần tìm kiếm tức thì (Lookup).	Xử lý va chạm.
Dijkstra	O(E + V log V)	Tìm đường ngắn nhất (Map).	Không dùng cho cạnh âm.

DAY 40🇯🇵 アルゴリズム総復習

40%