Algorithm Solutions — Simple Explanation About Time Complexity & Big O
Algorithm là gì? Time complexity là gì? Big O là gì?
Chắc hẵn 3 khái niệm này thực sự quá quen thuộc đổi với những bạn học về mảng công nghệ thông tin
Nhưng hiểu 1 điều có thể vài bạn mặc dù “đã biết” nhưng mà để hiểu rõ khái niệm thì thực tế lại không nhiều
1. Algorithm
- Từ những yêu cầu (requirements) hoặc vấn đề (issues) chúng ta cần 1 cách để giải quyết
- Thì những logic và các điều kiện (condition) sẽ tạo ra 1 giải thuật (Algorithm)
- Ví dụ yêu cầu là cần tính toán tổng km cho 1 chuyến đi: sẽ có nhiều yếu tố để tạo ra 1 giải thuật là phương tiện, điều kiện thời tiết, …
2. Time complexity
- Thời gian để thử hiện 1 giải thuật
- Ví dụ tốn 3 giây để tính toán tổng km cho 1 chuyến đi
3. Big O
- Độ phức tạp của giải thuật (thuật toán)
- Dùng để so sánh mức độ hiểu quả của giải thuật — Thời gian chạy sẽ phụ thuộc vào input, input càng lớn thì phải tốn nhiều thời gian hơn để xử lý
Các ví dụ tiêu biểu
1. O(1) — Chỉ cần 1 bước là tính ra được kết quả
console.log(items[index]);2. O(n) — Trường hợp xấu nhất là phải duyệt qua hết mảng
for (const item: items) {
console.log(item);
}3. O(n²) — Có 2 vòng lập cùng sử lý
for (const firstItem: items) {
for (const secondItem: items) {
console.log(firstItem + ", " + secondItem);
}
}4. O(log n) — Không cần duyệt hết mảng mà chỉ cần 1 phần — Binary search
Có thể tìm hiểu thử bài toán này: https://leetcode.com/problems/search-insert-position/
Cách giải: https://www.youtube.com/watch?v=K-RYzDZkzCI
Ngoài ra, để tìm hiểu kĩ hơn có các nguồn tài liệu có thể tham khảm như
- https://techmaster.vn/posts/34982/hieu-don-gian-ve-khai-niem-big-o-trong-lap-trinh
- https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
#indexing #timecomplexity #algorithmsolutions #sharing
