Tóm tắt¶

Điểm lại trọng tâm¶

Đánh giá hiệu suất thuật toán

Hiệu suất thời gian và hiệu suất không gian là hai chỉ số đánh giá chính để đo lường chất lượng của thuật toán.
Chúng ta có thể đánh giá hiệu suất thuật toán thông qua thực nghiệm (thử nghiệm thực tế), nhưng rất khó loại bỏ ảnh hưởng của môi trường kiểm thử, và việc này tiêu tốn nhiều tài nguyên tính toán.
Phân tích độ phức tạp có thể khắc phục các hạn chế của kiểm thử thực tế. Kết quả phân tích áp dụng được cho mọi nền tảng chạy thuật toán, đồng thời có thể chỉ ra hiệu suất của thuật toán dưới các quy mô dữ liệu khác nhau.

Độ phức tạp thời gian

Độ phức tạp thời gian được sử dụng để đo lường xu hướng thời gian chạy của thuật toán khi lượng dữ liệu tăng lên. Nó có thể đánh giá hiệu suất thuật toán một cách hiệu quả, nhưng trong một số trường hợp có thể không còn hiệu dụng, ví dụ khi lượng dữ liệu đầu vào nhỏ hoặc khi các độ phức tạp thời gian là như nhau, khiến việc so sánh chính xác hiệu suất thuật toán trở nên bất khả thi.
Độ phức tạp thời gian trong trường hợp xấu nhất được biểu diễn bằng ký hiệu \(O\) lớn (Big \(O\)), tương ứng với giới hạn trên tiệm cận của hàm số, phản ánh mức độ tăng trưởng của số lượng thao tác \(T(n)\) khi \(n\) tiến tới dương vô cùng.
Việc tính toán độ phức tạp thời gian gồm hai bước: đầu tiên là đếm số lượng thao tác, sau đó xác định giới hạn trên tiệm cận.
Các độ phức tạp thời gian phổ biến sắp xếp từ thấp đến cao gồm có \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\), \(O(2^n)\) và \(O(n!)\), v.v.
Độ phức tạp thời gian của một số thuật toán không cố định mà phụ thuộc vào sự phân bố của dữ liệu đầu vào. Độ phức tạp thời gian được chia thành độ phức tạp thời gian trong trường hợp xấu nhất, tốt nhất và trung bình. Độ phức tạp thời gian trong trường hợp tốt nhất hầu như không được sử dụng vì dữ liệu đầu vào thường phải đáp ứng các điều kiện cực kỳ nghiêm ngặt mới đạt được trường hợp tốt nhất.
Độ phức tạp thời gian trung bình phản ánh hiệu suất chạy của thuật toán dưới dữ liệu đầu vào ngẫu nhiên, gần nhất với hiệu năng thực tế của thuật toán. Việc tính toán độ phức tạp thời gian trung bình yêu cầu thống kê phân bố dữ liệu đầu vào cũng như kỳ vọng toán học sau khi tổng hợp.

Độ phức tạp không gian

Độ phức tạp không gian phục vụ mục đích tương tự như độ phức tạp thời gian, dùng để đo lường xu hướng sử dụng bộ nhớ của thuật toán khi lượng dữ liệu tăng lên.
Không gian bộ nhớ liên quan đến quá trình chạy của thuật toán có thể chia thành không gian đầu vào (input space), không gian tạm thời (temporary space) và không gian đầu ra (output space). Thông thường, không gian đầu vào không được tính vào độ phức tạp không gian. Không gian tạm thời có thể được chia thành dữ liệu tạm thời, không gian stack frame (khung ngăn xếp) và không gian lệnh, trong đó không gian stack frame thường chỉ ảnh hưởng đến độ phức tạp không gian trong các hàm đệ quy.
Chúng ta thường chỉ quan tâm đến độ phức tạp không gian trong trường hợp xấu nhất, tức là thống kê độ phức tạp không gian của thuật toán dưới dữ liệu đầu vào xấu nhất và thời điểm chạy tốn bộ nhớ nhất.
Các độ phức tạp không gian phổ biến sắp xếp từ thấp đến cao gồm có \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n^2)\) và \(O(2^n)\), v.v.

Q & A¶

Q: Độ phức tạp không gian của đệ quy đuôi có phải là \(O(1)\) không?

Về mặt lý thuyết, độ phức tạp không gian của hàm đệ quy đuôi có thể được tối ưu hóa về \(O(1)\). Tuy nhiên, hầu hết các ngôn ngữ lập trình (như Java, Python, C++, Go, C#, v.v.) không hỗ trợ tự động tối ưu hóa đệ quy đuôi, do đó độ phức tạp không gian thường được coi là \(O(n)\).

Q: Sự khác biệt giữa hai thuật ngữ hàm (function) và phương thức (method) là gì?

Một hàm (function) có thể được thực thi độc lập, với tất cả các tham số được truyền một cách tường minh. Một phương thức (method) được liên kết với một đối tượng, được liên kết ngầm với đối tượng gọi nó và có thể thao tác trên dữ liệu chứa trong thực thể của lớp (class instance).

Dưới đây là một số ví dụ sử dụng các ngôn ngữ lập trình phổ biến để minh họa:

Ngôn ngữ C là ngôn ngữ lập trình thủ tục, không có khái niệm hướng đối tượng, vì vậy chỉ có hàm. Tuy nhiên, chúng ta có thể mô phỏng lập trình hướng đối tượng bằng cách tạo cấu trúc (struct), và các hàm liên kết với cấu trúc tương đương với phương thức trong các ngôn ngữ lập trình khác.
Java và C# là các ngôn ngữ lập trình hướng đối tượng, trong đó các khối mã (phương thức) thường là một phần của một lớp. Các phương thức tĩnh (static method) hoạt động giống như hàm vì chúng được liên kết với lớp và không thể truy cập các biến thực thể (instance variable) cụ thể.
C++ và Python hỗ trợ cả lập trình thủ tục (hàm) và lập trình hướng đối tượng (phương thức).

Q: Hình minh họa "các loại độ phức tạp không gian phổ biến" có phản ánh kích thước tuyệt đối của không gian bị chiếm dụng không?

Không, hình minh họa hiển thị độ phức tạp không gian, phản ánh xu hướng tăng trưởng thay vì kích thước tuyệt đối của không gian bị chiếm dụng.

Giả sử với \(n = 8\), bạn có thể thấy giá trị của mỗi đường cong không khớp với hàm số tương ứng. Điều này là do mỗi đường cong đều chứa một số hạng tự do (constant term) dùng để nén phạm vi giá trị vào một khoảng hiển thị dễ nhìn.

Trong thực tế, do chúng ta thường không biết độ phức tạp "số hạng tự do" của mỗi phương thức là bao nhiêu, nên thông thường không thể chỉ dựa vào độ phức tạp để chọn ra giải pháp tối ưu cho trường hợp \(n = 8\). Tuy nhiên, với \(n = 8^5\) thì việc lựa chọn rất dễ dàng, lúc này xu hướng tăng trưởng đã đóng vai trò chủ đạo.

Q: Có trường hợp nào mà thuật toán được thiết kế để đánh đổi thời gian (hoặc không gian) dựa trên các tình huống sử dụng thực tế không?

Trong ứng dụng thực tế, hầu hết các trường hợp sẽ chọn đánh đổi không gian lấy thời gian. Ví dụ với chỉ mục cơ sở dữ liệu (database index), chúng ta thường chọn xây dựng cây B+ hoặc chỉ mục băm (hash index), chiếm nhiều không gian bộ nhớ để đổi lấy các truy vấn hiệu quả với độ phức tạp \(O(\log n)\) hoặc thậm chí là \(O(1)\).

Trong các tình huống tài nguyên không gian hạn chế, thời gian có thể bị đánh đổi lấy không gian. Ví dụ trong phát triển hệ thống nhúng, bộ nhớ thiết bị rất quý giá, các kỹ sư có thể từ bỏ việc sử dụng bảng băm (hash table) và chọn tìm kiếm tuần tự trên mảng để tiết kiệm bộ nhớ, với cái giá phải trả là tốc độ tìm kiếm chậm hơn.