Độ phức tạp thuật toán: Ảnh hưởng của O lớn tới performance

Bất cứ ai trong lúc tối ưu code ruby luôn nhập tâm nằm lòng các nguyên tắc:

• Tìm kiếm trên hash luôn nhanh hơn tìm kiếm trên array
• Tránh các vòng lặp lồng nhau
• Hạn chế query database khi hiển thị một list trên view

Các nguyên tắc này rất hiệu quả, dễ nhớ và dễ áp dụng. Nhưng không việc không hiểu được vì sao lại có những quy luật đấy, và chúng hoạt động như thế nào, ta sẽ dễ mắc phải những sai lầm không đáng có. Bản thân tôi đã gặp trường hợp coder sử dụng hash để tăng tốc nhưng lại tra cứu hash như một array, làm triệt tiêu tất cả lợi thế tốc độ của hash.

Thật may là tôi ngành khoa học máy tính tôi theo học đại học lại lấy những lý thuyết về độ phức tạp thuật toán làm nền tảng và chữ O lớn là mục tiêu nghiên cứu, nên dù muốn hay không, tôi vẫn luôn bị ám ảnh về việc mỗi dòng code viết ra, O lớn là bao nhiêu và làm thế nào để làm cho O lớn nhỏ nhất.

Bài viết này nói về khái niệm O lớn trong thực tế, hy vọng cung cấp cho mọi người cái nhìn cơ bản nhất về O lớn và áp dụng trong các bài toán thực tế. Code trong bài được thể hiện bằng Ruby, nhưng lý thuyết về độ phức tạp thuật toán có thể được áp dụng ở tất cả các ngôn ngữ.

O lớn là gì?

Chắc hẳn sau khi đọc qua mấy dòng trên trong đầu bạn sẽ nảy ra nhiều câu hỏi: O lớn là gì? O lớn có gì mà khiến cho tay viết bài ám ảnh đến vậy? O lớn là ký hiệu mô tả độ phức tạp của một thuật toán, hay nói đơn giản là performace của code trên một database bất kỳ. O lớn đại diện cho trường hợp xấu nhất có thể sảy ra, hay cận trên của thuật toán. Cùng với O lớn, còn có các ký hiệu Ω(omega) và Θ(teta) đại diện cho trường hợp tốt nhất và trường hợp trung bình.

Performance thường được hiểu là khái niệm bao gồm hai tiêu chí: tốc độ xử lý và bộ nhớ cần sử dụng. Trong ngành khoa học máy tính hai khái niệm này thường được gọi là "độ phức tạp thời gian" và "độ phức tạp không gian". Khái niệm O lớn có thể dùng cho cả hai loại độ phức tạp trên, nhưng với độ lớn gần như vô hạn của phần cứng bộ nhớ và mục tiêu chính của chúng ta thường là cải thiện tốc độ, nên O lớn thường được dùng với khái niệm thời gian.

Với những bài toán nhỏ, O lớn không ảnh hưởng nhiều đến thời gian tính toán. Nhưng khi lượng dữ liệu tăng dần, O lớn sẽ quyết định tốc độ xử lý tăng tương ứng bao nhiêu lần.

Dưới đây là một bảng tra cứu nhanh về các giá trị O lớn thường gặp, rank đánh giá O lớn trong bảng chính là cái mặt của bạn khi gặp những thuật toán như thế.