Độ phức tạp thấp (low complexity) là gì?

Tiếng Anhlow complexity

Độ phức tạp thấp (low complexity) là đặc tính của thuật toán, phương pháp xử lý tín hiệu hoặc kiến trúc hệ thống được thiết kế nhằm giảm thiểu lượng tài nguyên tính toán, dung lượng bộ nhớ, độ trễ và năng lượng tiêu thụ theo kích thước đầu vào mà vẫn duy trì hiệu năng chấp nhận được.

Kỹ thuật và công nghệ Cập nhật 18/11/2026

Độ phức tạp thấp (low complexity) là đặc tính của thuật toán, phương pháp xử lý tín hiệu hoặc kiến trúc hệ thống được thiết kế nhằm giảm thiểu lượng tài nguyên tính toán, dung lượng bộ nhớ, độ trễ và năng lượng tiêu thụ theo kích thước đầu vào, đồng thời vẫn duy trì mức hiệu năng chấp nhận được. Khác với bài toán vốn đơn giản, khái niệm này thường gắn với các kỹ thuật xấp xỉ, phân rã hoặc tái cấu trúc bài toán vốn có chi phí lớn để đáp ứng ràng buộc phần cứng và thời gian thực. Bài viết trình bày khái niệm theo trọng tâm kỹ thuật và công nghệ thông tin, phân biệt các nghĩa khác nhau giữa các ngành, phân tích các thước đo đánh giá, phương pháp thiết kế, ứng dụng thực tế và những giới hạn trong triển khai.

Khái niệm và đa nghĩa theo ngành khoa học

Trong kỹ thuật và khoa học tính toán, độ phức tạp thấp không mang một ngưỡng số học cố định duy nhất mà là thuộc tính tương đối khi so sánh một phương pháp cải tiến với phương pháp chuẩn hoặc tối ưu lý thuyết. Một thuật toán hay bộ xử lý được gọi là có độ phức tạp thấp khi nó loại bỏ hoặc thay thế được các phép toán bậc cao tốn kém (như tìm kiếm vét cạn theo cấp số nhân hoặc nghịch đảo ma trận trực tiếp) bằng các bước tính nhẹ hơn, dễ song song hóa hơn trên phần cứng thực thi.

Tuy nhiên, thuật ngữ độ phức tạp thấp được dùng với các sắc thái khác nhau tùy theo lĩnh vực nghiên cứu:

  • Kỹ thuật truyền thông, xử lý tín hiệu và học máy trên thiết bị biên: Chỉ các bộ phát hiện tín hiệu, bộ mã hóa nguồn hoặc kênh, bộ giải mã và mô hình mạng nơ-ron được thiết kế để cắt giảm số phép tính, bộ nhớ đệm và công suất tiêu thụ trên chip xử lý tín hiệu số (DSP), mạch tích hợp cỡ rất lớn (VLSI) hay vi điều khiển.
  • Khoa học máy tính lý thuyết: Theo giáo trình Computational Complexity của Arora và Barak (2009), chi phí thuật toán được đặc trưng bằng các ký pháp tiệm cận OO lớn, Ω\Omega lớn và Θ\Theta lớn. Các thuật toán có thời gian chạy bị chặn trên bởi đa thức dạng O(nk)O(n^k) (với nn là kích thước đầu vào và kk là hằng số) làm nền tảng cho lớp bài toán hiệu quả P, phân biệt với tăng trưởng hàm mũ O(2n)O(2^n); trong thực hành lập trình, các mức hằng số O(1)O(1), logarit O(log⁡n)O(\log n), tuyến tính O(n)O(n) hoặc O(nlog⁡n)O(n \log n) thường được xem là có độ phức tạp thấp.
  • Tin sinh học và sinh học phân tử: Thuật ngữ vùng có độ phức tạp thấp (low-complexity regions, LCRs) mang ý nghĩa hoàn toàn khác về cấu trúc dữ liệu sinh học. Theo tổng quan của Mier và cộng sự (2019), LCRs trong trình tự protein là các đoạn trình tự chứa ít loại axit amin hơn so với phân bố trung bình hoặc có sự thiên lệch thành phần (composition bias), chứ không phải thước đo tốc độ thuật toán.

Thước đo đánh giá độ phức tạp thấp

Để khẳng định một giải pháp đạt độ phức tạp thấp một cách khách quan, giới nghiên cứu kỹ thuật không chỉ dựa vào thời gian chạy đo bằng đồng hồ trên một máy tính đơn lẻ mà kết hợp nhiều thước đo phân tích và đo đạc phần cứng.

1. Độ phức tạp tiệm cận và bậc tăng trưởng phép toán

Độ phức tạp tiệm cận mô tả tốc độ tăng của số phép toán cơ bản hoặc dung lượng bộ nhớ khi kích thước đầu vào nn hoặc số lượng người dùng KK tăng lên. Ví dụ, trong xử lý tín hiệu đa ăng-ten quy mô lớn (Massive MIMO), phép nghịch đảo ma trận trực tiếp của các bộ phát hiện tuyến tính chuẩn có bậc tăng trưởng lập phương O(K3)O(K^3). Khi chuyển sang các bộ giải lặp xấp xỉ chỉ dùng phép nhân ma trận với vector, chi phí mỗi vòng lặp giảm xuống bậc bình phương O(K2)O(K^2), tạo ra mức tiết kiệm phép tính rõ rệt khi KK lớn (Albreem và cộng sự, 2019).

2. Số phép tính dấu phẩy động (FLOPs) và dung lượng bộ nhớ

Trong học sâu và xử lý ảnh, khối lượng tính toán thường được định lượng bằng tổng số phép tính dấu phẩy động (floating-point operations, FLOPs), bên cạnh dung lượng bộ nhớ tĩnh (lưu trữ tham số trọng số) và bộ nhớ động (lưu trữ các bản đồ đặc trưng trung gian khi suy luận). Các thiết bị biên như nút cảm biến không dây hay vi điều khiển có giới hạn chặt về bộ nhớ truy cập ngẫu nhiên tĩnh (SRAM) và bộ nhớ flash, do đó giảm bộ nhớ thường quan trọng ngang bằng với giảm số phép nhân cộng (Liu và cộng sự, 2024).

3. Cường độ vận hành và chi phí truy cập bộ nhớ

Một điểm dễ hiểu nhầm trong thiết kế thuật toán là cho rằng giảm FLOPs luôn đồng nghĩa với giảm thời gian thực thi. Mô hình Roofline do Williams, Waterman và Patterson (2009) công bố thiết lập giới hạn hiệu năng phần cứng dựa trên đại lượng cường độ vận hành (operational intensity, tác giả chủ ý phân biệt với arithmetic intensity vốn đo lưu lượng giữa bộ xử lý và bộ nhớ đệm cache), được định nghĩa là tỷ số giữa số phép toán thực hiện được trên mỗi byte dữ liệu truyền qua bộ nhớ chính (DRAM):

I=FLOPsBytesI = \frac{\text{FLOPs}}{\text{Bytes}}

Trong biểu thức trên, II là cường độ vận hành (tính theo số phép toán dấu phẩy động trên mỗi byte dữ liệu), tử số là tổng số phép toán thực hiện và mẫu số là lượng byte dữ liệu trao đổi giữa bộ nhớ đệm và bộ nhớ chính DRAM. Theo mô hình Roofline (Williams và cộng sự, 2009), nếu II thấp, hệ thống rơi vào vùng giới hạn bởi băng thông bộ nhớ (memory-bound): bộ xử lý phải chờ nạp dữ liệu từ bộ nhớ nên không đạt được năng lực tính toán đỉnh (compute-bound). Tổng quan của Liu và cộng sự (2024) cũng xác nhận rằng số FLOPs thấp không tự động chuyển hóa thành độ trễ thực thi thấp trên phần cứng thật do chi phí truy cập bộ nhớ (memory access cost) và các điểm nghẽn song song hóa.

Các kỹ thuật đạt độ phức tạp thấp trong khoa học và kỹ thuật

Các phương pháp giảm độ phức tạp thường tác động vào cấu trúc toán học của bài toán hoặc vào kiến trúc biểu diễn dữ liệu và mô hình tính toán.

1. Xấp xỉ nghịch đảo ma trận và giải lặp trong truyền thông không dây

Ở tầng vật lý của hệ thống truyền thông vô tuyến Massive MIMO, bài toán tách tín hiệu đường lên trên trạm gốc có số lượng lớn phần tử ăng-ten khiến các bộ thu tối ưu theo tiêu chuẩn hợp lý cực đại (maximum likelihood) đòi hỏi chi phí tính toán quá cao. Ngay cả các bộ phát hiện tuyến tính chuẩn như ép không (Zero-Forcing, ZF) hay sai số bình phương trung bình tối thiểu (MMSE) cũng vướng nút thắt nghịch đảo ma trận cỡ K×KK \times K với độ phức tạp O(K3)O(K^3) (Albreem và cộng sự, 2019).

Theo khảo sát của Albreem, Juntti và Shahabuddin (2019), hai hướng tiếp cận độ phức tạp thấp phổ biến trong thiết kế phần cứng VLSI là:

  • Khai triển chuỗi Neumann (Neumann series): Phân tách ma trận hệ thống GG thành tổng của ma trận đường chéo chính DD và ma trận các phần tử ngoài đường chéo EE theo phương trình G=D+EG = D + E. Nghịch đảo G−1G^{-1} được xấp xỉ bằng tổng hữu hạn các lũy thừa của tích −D−1E-D^{-1}E nhân với D−1D^{-1}, loại bỏ hoàn toàn phép nghịch đảo ma trận đầy đủ và duy trì luồng dữ liệu tất định rất thuận lợi cho mạch VLSI.
  • Phương pháp giải lặp ẩn (Jacobi, Gauss-Seidel): Thay vì tính tường minh ma trận nghịch đảo, bộ thu giải trực tiếp hệ phương trình tuyến tính bằng các bước lặp nhân ma trận với vector, đưa độ phức tạp mỗi vòng lặp về mức O(K2)O(K^2).

2. Tối ưu cấu trúc mã hóa kênh và xử lý dữ liệu bộ nhớ thấp

Trong lý thuyết mã hóa sửa lỗi và nén ảnh cho mạng cảm biến, mục tiêu là rút ngắn đường dẫn giải mã hoặc loại bỏ các vòng lặp kiểm tra dư thừa mà không làm suy giảm độ tin cậy truyền tin:

  • Mã hóa kênh độ phức tạp thấp: Trong nghiên cứu của Sholiyi và O'Farrell (2022) về mã Turbo vector không đều (Irregular Vector Turbo Codes, iVTC), các bit thông tin tham gia vào số lượng phân đoạn lưới trellis khác nhau và chỉ được mã hóa theo một chiều ngang hoặc dọc thay vì mã hóa hai chiều như mã khối Turbo (BTC). Thiết kế này chỉ cần một bộ giải mã đầu vào mềm - đầu ra mềm, giúp giảm độ phức tạp tính toán so với BTC tại cùng xác suất lỗi bit 10−510^{-5}, đồng thời đạt lợi ích mã hóa 1,281,28 dB với điều chế 64QAM và hoạt động trong khoảng 0,490,49 dB so với giới hạn dung lượng nhị phân trên kênh nhiễu trắng cộng Gauss (AWGN).
  • Nén ảnh cho mạng cảm biến đa phương tiện không dây (WMSNs) và IoT: Thuật toán mã hóa ảnh wavelet bộ nhớ bằng không ZM-SPECK vốn tiêu tốn nhiều thời gian cho bước so sánh từng phần tử khối với ngưỡng ở mỗi mặt phẳng bit. Nghiên cứu của Tausif, Khan và Pinheiro (2023) đã khắc phục bằng cách tìm và lưu trước giá trị độ lớn hệ số cực đại trong mỗi dải con ngay lúc tính biến đổi Wavelet rời rạc (DWT). Kết quả mô phỏng cho thấy giải pháp này giảm khoảng 2929% độ phức tạp tính toán của ZM-SPECK trong khi vẫn giữ nguyên chính xác tỷ số tín hiệu đỉnh trên nhiễu (PSNR).

3. Thiết kế mô hình nhẹ và nén mạng học sâu trên thiết bị biên

Theo tổng quan của Liu và cộng sự (2024) về học sâu nhẹ cho môi trường hạn chế tài nguyên, các kỹ thuật đưa mô hình mạng nơ-ron về trạng thái độ phức tạp thấp được phân thành 3 nhóm trụ cột chính:

  1. Thiết kế mô hình nhẹ (Lightweight Model Design): Thay thế tích chập chuẩn bằng tích chập tách biệt theo chiều sâu (depthwise separable convolution), khối dư đảo ngược hoặc cơ chế chú ý hiệu quả nhằm giảm số tham số và phép nhân cộng ngay từ cấu trúc lớp.
  2. Phương pháp nén mô hình (Model Compression Methods): Gồm cắt tỉa mạng (pruning, loại bỏ kết nối hoặc kênh ít đóng góp), lượng tử hóa (quantization, biểu diễn trọng số và kích hoạt ở độ chính xác bit thấp hơn), chưng cất tri thức (knowledge distillation, truyền hành vi từ mô hình lớn sang mô hình nhỏ), tìm kiếm kiến trúc nơ-ron (neural architecture search, NAS) cùng các kỹ thuật giảm tham số như phân rã hạng thấp (low-rank factorization).
  3. Chiến lược tăng tốc phần cứng (Hardware Acceleration Strategies): Tập trung vào thiết kế kiến trúc phần cứng tính toán, tối ưu luồng dữ liệu và tính cục bộ của bộ nhớ đệm, cùng thư viện và đồng thiết kế phần cứng - phần mềm để khai thác hiệu quả mô hình nhẹ trên thiết bị biên.

Ứng dụng thực tế và bối cảnh nghiên cứu tại Việt Nam

Các thuật toán và kiến trúc độ phức tạp thấp đóng vai trò nền tảng trong nhiều hệ thống công nghiệp và nghiên cứu ứng dụng đòi hỏi xử lý thời gian thực hoặc vận hành bằng pin:

  • Hệ thống radar MIMO và xử lý tín hiệu tại Việt Nam: Trong lĩnh vực kỹ thuật radar, xử lý thích nghi không gian - thời gian (Space-Time Adaptive Processing, STAP) giúp triệt nhiễu và tán xạ nhưng đòi hỏi ước lượng và nghịch đảo ma trận hiệp phương sai nhiễu có kích thước rất lớn, gây bùng nổ khối lượng tính toán đến mức có thể không tính được theo thời gian thực. Nghiên cứu của Đào Minh Hưng và Mai Xuân Bình (2018) công bố trên Tạp chí Khoa học và Công nghệ - Đại học Đà Nẵng đã đề xuất áp dụng phép biến đổi tuyến tính để làm thưa ma trận hiệp phương sai nhiễu trong radar MIMO kết hợp, qua đó giảm độ phức tạp tính toán ma trận mà vẫn bảo đảm hiệu quả phát hiện mục tiêu.
  • Hạ tầng viễn thông đa ăng-ten quy mô lớn (Massive MIMO): Tại các trạm gốc trang bị số lượng lớn ăng-ten và chuỗi tần số vô tuyến (RF), các bộ tách tín hiệu dựa trên giải lặp O(K2)O(K^2) giúp giảm mạnh chi phí phần cứng so với phép nghịch đảo ma trận trực tiếp O(K3)O(K^3) mà bộ thu phi tuyến tối ưu khó đáp ứng (Albreem và cộng sự, 2019).
  • Mạng cảm biến IoT và thiết bị đeo thông minh: Việc tích hợp bộ mã hóa ảnh wavelet giảm 2929% độ phức tạp của Tausif và cộng sự (2023) hoặc các mô hình TinyML (Liu và cộng sự, 2024) giúp kéo dài tuổi thọ pin cho nút cảm biến giám sát môi trường, nông nghiệp thông minh và thiết bị y tế di động mà không cần truyền dữ liệu thô dung lượng lớn lên đám mây.

So sánh độ phức tạp thấp với các hướng tiếp cận khác

Bảng dưới đây đối chiếu đặc trưng của thiết kế độ phức tạp thấp với phương pháp tối ưu lý thuyết đầy đủ và với khái niệm độ phức tạp thấp trong tin sinh học để tránh nhầm lẫn ngữ cảnh:

Tiêu chí đối chiếu Phương pháp chuẩn / Tối ưu lý thuyết Thiết kế độ phức tạp thấp (Kỹ thuật & Thuật toán) Vùng độ phức tạp thấp (Tin sinh học - LCRs)
Mục tiêu cốt lõi Đạt độ chính xác hoặc cận tối ưu lý thuyết cao nhất bất chấp chi phí tính toán. Giảm phép toán, bộ nhớ, độ trễ và năng lượng về mức phần cứng đáp ứng được. Mô tả tính đơn điệu hoặc thiên lệch thành phần trong trình tự protein (Mier và cộng sự, 2019).
Cơ chế điển hình Tìm kiếm vét cạn, nghịch đảo ma trận trực tiếp O(K3)O(K^3), mạng sâu đầy đủ tham số. Xấp xỉ lặp O(K2)O(K^2), làm thưa ma trận, lượng tử hóa, cắt tỉa mạng, lưu cực đại dải con. Sự lặp lại hoặc giàu một số axit amin nhất định so với phân bố trung bình của trình tự.
Thước đo đánh giá chính Sai số tối thiểu, xác suất lỗi cực tiểu hoặc độ chính xác cao nhất. Thời gian tiệm cận, FLOPs, chi phí truy cập bộ nhớ (MAC), cường độ vận hành, độ trễ thực. Chỉ số entropy thành phần và mức thiên lệch axit amin trong cửa sổ trình tự.
Rủi ro đặc thù Quá tải bộ nhớ, không chạy được thời gian thực, tiêu tốn năng lượng lớn. Có thể mất một phần độ chính xác hoặc vẫn nghẽn nếu bị giới hạn băng thông bộ nhớ. Gây khớp giả trong công cụ bắt cặp trình tự nếu không lọc đúng cách.

Hạn chế, đánh đổi và vấn đề còn mở

Tính đến năm 2024, các công trình tổng quan về kiến trúc nhẹ và hiệu năng phần cứng chỉ ra nhiều giới hạn thực tế cho thấy độ phức tạp thấp không phải là đặc tính miễn phí hay chỉ phụ thuộc vào một con số đơn lẻ:

  • Khoảng cách giữa FLOPs lý thuyết và độ trễ thực tế: Nghiên cứu tổng quan của Liu và cộng sự (2024) chỉ ra rằng số FLOPs thấp không tự động dẫn đến độ trễ thực thi thấp trên phần cứng thật do chi phí truy cập bộ nhớ và mức độ song song hóa hạn chế. Khi cường độ vận hành quá thấp, phần cứng sẽ bị nghẽn ở băng thông bộ nhớ như mô tả bởi mô hình Roofline (Williams và cộng sự, 2009), khiến thuật toán có ít phép toán số học lại chạy chậm hơn thuật toán tối ưu tốt việc tái sử dụng dữ liệu trong bộ nhớ đệm.
  • Đánh đổi độ chính xác và điều kiện hội tụ: Các phương pháp xấp xỉ độ phức tạp thấp trong xử lý tín hiệu như khai triển chuỗi Neumann hay các bộ giải lặp có thể suy giảm chất lượng phát hiện (tăng tỷ lệ lỗi bit) hoặc hội tụ chậm nếu số vòng lặp bị cắt quá ngắn hoặc ma trận kênh truyền có điều kiện xấu (Albreem và cộng sự, 2019).
  • Độ nhạy cảm phần cứng khi nén mô hình: Trong học sâu biên, việc cắt tỉa phi cấu trúc hoặc lượng tử hóa sâu có thể giảm mạnh số lượng tham số trên lý thuyết, nhưng nếu bộ tăng tốc phần cứng không hỗ trợ tính toán thưa hoặc phép tính số nguyên bit thấp, mức tăng tốc thực tế sẽ rất hạn chế (Liu và cộng sự, 2024).
  • Thiếu ngưỡng định lượng phổ quát liên ngành: Chưa tồn tại một ngưỡng số phép toán tuyệt đối thống nhất cho mọi hệ thống để phân định ranh giới giữa "độ phức tạp thấp" và "độ phức tạp cao". Một thuật toán O(K2)O(K^2) có thể đủ nhẹ cho trạm gốc viễn thông nhưng vẫn quá nặng đối với nút cảm biến vi điều khiển chạy pin nhiều năm.

Câu hỏi thường gặp

Độ phức tạp thấp khác gì với một hệ thống hoặc thuật toán đơn giản?

Một hệ thống đơn giản giải quyết bài toán vốn ít bước tính ngay từ đầu, còn thiết kế độ phức tạp thấp thường nhắm vào các bài toán có chi phí tính toán gốc rất cao (như nghịch đảo ma trận lớn hay suy luận mạng nơ-ron sâu). Các kỹ sư dùng xấp xỉ lặp, phân rã cấu trúc hoặc nén mô hình để hạ chi phí thực thi về mức phần cứng đáp ứng được mà vẫn giữ hiệu năng gần tối ưu.

Tại sao giảm số phép tính FLOPs đôi khi không làm mô hình chạy nhanh hơn trên phần cứng?

FLOPs chỉ đo tổng số phép toán số học lý thuyết, không phản ánh chi phí truyền dữ liệu giữa bộ nhớ chính và bộ xử lý. Theo mô hình Roofline (2009) và tổng quan học sâu nhẹ (2024), nếu cường độ vận hành thấp, hệ thống sẽ bị nghẽn bởi băng thông bộ nhớ và độ trễ thực tế vẫn cao.

Làm thế nào để giảm độ phức tạp tính toán trong xử lý tín hiệu Massive MIMO?

Thay vì thực hiện nghịch đảo ma trận trực tiếp với độ phức tạp bậc lập phương O(K^3) theo số người dùng K, các bộ phát hiện đường lên sử dụng phương pháp xấp xỉ chuỗi Neumann hoặc các bộ giải lặp như Jacobi và Gauss-Seidel. Cách tiếp cận này thay phép nghịch đảo bằng nhân ma trận-vector, giảm độ phức tạp mỗi vòng lặp xuống mức O(K^2).

Thuật ngữ vùng độ phức tạp thấp (low-complexity regions) trong tin sinh học có giống khái niệm này không?

Không. Trong tin sinh học và sinh học phân tử, vùng độ phức tạp thấp (LCRs) chỉ các đoạn trình tự protein có tính lặp lại hoặc thiên lệch thành phần axit amin so với phân bố trung bình, không phải thước đo tốc độ hay tài nguyên của thuật toán.

Tài liệu tham khảo

  1. Arora, S., & Barak, B. (2009). Computational Complexity. Cambridge University Press. DOI: 10.1017/CBO9780511804090
  2. Albreem, M. A., Juntti, M., & Shahabuddin, S. (2019). Massive MIMO Detection Techniques: A Survey. IEEE Communications Surveys & Tutorials. DOI: 10.1109/COMST.2019.2935810
  3. Sholiyi, A. O., & O’Farrell, T. (2022). Irregular Vector Turbo Codes with low complexity. EURASIP Journal on Wireless Communications and Networking. DOI: 10.1186/s13638-022-02115-5
  4. Tausif, M., Khan, E., & Pinheiro, A. (2023). Computationally efficient wavelet-based low memory image coder for WMSNs/IoT. Multidimensional Systems and Signal Processing. DOI: 10.1007/s11045-023-00878-8
  5. Đào Minh Hưng & Mai Xuân Bình (2018). Nâng cao hiệu quả phát hiện mục tiêu trong hệ thống radar MIMO kết hợp dựa vào xử lý thích nghi không gian - thời gian với độ phức tạp tính toán thấp. Tạp chí Khoa học và Công nghệ - Đại học Đà Nẵng. Nguồn
  6. Liu, H.-I., Galindo, M., Xie, H., Wong, L.-K., Shuai, H.-H., Li, Y.-H., & Cheng, W.-H. (2024). Lightweight Deep Learning for Resource-Constrained Environments: A Survey. ACM Computing Surveys, 56(10). DOI: 10.1145/3657282
  7. Williams, S., Waterman, A., & Patterson, D. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures. Communications of the ACM, 52(4), 65-76. DOI: 10.1145/1498765.1498785
  8. Mier, P., Paladin, L., Tamana, S., et al. (2019). Disentangling the complexity of low complexity proteins. Briefings in Bioinformatics, 21(2), 458-472. DOI: 10.1093/bib/bbz007