Phân tích thuật toán

Trong khoa học máy tính, việc phân tích các thuật toán là xác định độ phức tạp tính toán của các thuật toán, đó là lượng thời gian, lượng lưu trữ và / hoặc các tài nguyên khác cần thiết để thực hiện chúng. Thông thường, điều này liên quan đến việc xác định hàm liên quan đến độ dài của đầu vào thuật toán với số bước cần thực hiện (độ phức tạp thời gian của nó) hoặc số lượng vị trí lưu trữ mà nó sử dụng (độ phức tạp không gian của nó). Một thuật toán được cho là hiệu quả khi các giá trị của hàm này nhỏ hoặc tăng chậm so với tăng của kích thước của đầu vào. Các đầu vào khác nhau có cùng độ dài có thể khiến thuật toán có hành vi khác nhau, do đó, các mô tả trường hợp tốt nhất, xấu nhất và trung bình đều cần được quan tâm trong thực tế. Khi không có yêu cầu khác, hàm mô tả hiệu suất của thuật toán thường là giới hạn trên, được xác định từ các trường hợp xấu nhất với thuật toán.
Thuật ngữ "phân tích thuật toán" được đặt ra bởi Donald Knuth. Phân tích thuật toán là một phần quan trọng của lý thuyết phức tạp tính toán rộng hơn, nó cung cấp các ước tính lý thuyết cho các tài nguyên cần thiết cho bất kỳ thuật toán nào giải quyết một vấn đề tính toán nhất định. Các ước tính này cung cấp một cái nhìn sâu sắc về các hướng tìm kiếm hợp lý cho các thuật toán hiệu quả.
Trong phân tích lý thuyết của các thuật toán, người ta thường ước tính độ phức tạp của chúng theo nghĩa tiệm cận, nghĩa là ước tính độ phức tạp của hàm với đầu vào lớn tùy ý. Ký hiệu Big O, ký hiệu Big-omega và ký hiệu Big-theta được sử dụng cho mục đích này. Chẳng hạn, tìm kiếm nhị phân được cho là chạy theo một số bước tỷ lệ với logarit của độ dài của danh sách được sắp xếp đang tìm kiếm, hoặc trong O (log (n)), thông thường "trong thời gian logarit ". Thông thường các ước tính tiệm cận được sử dụng vì các triển khai khác nhau của cùng một thuật toán có thể khác nhau về hiệu quả. Tuy nhiên, hiệu quả của bất kỳ hai triển khai "hợp lý" nào của một thuật toán nhất định có liên quan bởi một hằng số nhân được gọi là hằng số ẩn.
Các đo đạc độ hiệu quả chính xác (không tiệm cận) đôi khi có thể được tính toán nhưng chúng thường yêu cầu một số giả định nhất định liên quan đến việc thực hiện cụ thể của thuật toán, được gọi là mô hình tính toán. Một mô hình tính toán có thể được định nghĩa theo thuật ngữ của một máy tính trừu tượng, ví dụ: máy Turing và / hoặc bằng cách quy định rằng các hoạt động nhất định được thực hiện trong thời gian đơn vị. Ví dụ: nếu danh sách được sắp xếp mà chúng ta áp dụng tìm kiếm nhị phân có n phần tử và chúng ta có thể đảm bảo rằng mỗi lần tra cứu của một phần tử trong danh sách có thể được thực hiện trong 1 đơn vị thời gian, thì hầu hết cần  log₂ n + 1 đơn vị thời gian để trả về một kết quả.

Phân tích thời gian chạy

Phân tích thời gian chạy là một phân loại lý thuyết ước tính và dự đoán sự gia tăng thời gian chạy  của thuật toán khi kích thước đầu vào của nó (thường được ký hiệu là n) tăng. Hiệu quả thời gian chạy là một chủ đề rất được quan tâm trong khoa học máy tính: Một chương trình có thể mất vài giây, vài giờ hoặc thậm chí nhiều năm để hoàn thành việc thực thi, tùy thuộc vào thuật toán mà nó thực hiện. Mặc dù các kỹ thuật phân tích phần mềm có thể được sử dụng để đo thời gian chạy của thuật toán trong thực tế, chúng không thể cung cấp dữ liệu thời gian cho tất cả đầu vào có thể; cái sau chỉ có thể đạt được bằng các phương pháp lý thuyết của phân tích thời gian chạy.

Cấp độ tăng trưởng

Một cách không chính thức, một thuật toán có thể được cho là thể hiện tốc độ tăng trưởng theo cấp độ của một hàm toán học nếu vượt quá một kích thước đầu vào n, hàm nhân một hằng số dương cung cấp giới hạn trên hoặc giới hạn cho thời gian chạy của thuật toán đó. Nói cách khác, với kích thước đầu vào đã cho n lớn hơn một số n ₀ và hằng số c, thời gian chạy của thuật toán đó sẽ không bao giờ lớn hơn . Khái niệm này thường được thể hiện bằng cách sử dụng ký hiệu Big O. Ví dụ, do thời gian chạy của sắp xếp chèn tăng theo phương trình bậc hai khi kích thước đầu vào của nó tăng lên, nên sắp xếp chèn là theo thứ tự O (n ²).
Ký hiệu Big O là một cách thuận tiện để diễn tả trường hợp xấu nhất cho một thuật toán nhất định, mặc dù nó cũng có thể được sử dụng để diễn tả trường hợp trung bình — ví dụ: trường hợp xấu nhất cho quicksort là O (n ²), nhưng thời gian chạy trường hợp trung bình là O(n log n).

Phân tích tốc độ tăng trưởng của các nguồn lực khác

Phương pháp phân tích thời gian chạy cũng có thể được sử dụng để dự đoán tốc độ tăng trưởng khác, chẳng hạn như tiêu thụ không gian bộ nhớ. Ví dụ, xem xét mã giả sau đây quản lý và phân bổ lại mức sử dụng bộ nhớ theo chương trình dựa trên kích thước của tệp mà chương trình đó quản lý: 
 while (file vẫn mở)
  let n = kích thước của tệp
  for mỗi 100.000 kilobyte gia tăng kích thước tập tin
    nhân đôi số lượng bộ nhớ dự trữ 
Trong trường hợp này, khi kích thước tệp n tăng, bộ nhớ sẽ được tiêu thụ ở tốc độ tăng trưởng theo cấp số nhân, theo thứ tự O (2 ⁿ). Đây là tốc độ tăng trưởng cực kỳ nhanh và rất có thể không thể kiểm soát được đối với việc tiêu thụ tài nguyên bộ nhớ.

Sự liên quan

Phân tích thuật toán rất quan trọng trong thực tế vì việc sử dụng ngẫu nhiên hoặc vô ý của một thuật toán không hiệu quả có thể ảnh hưởng đáng kể đến hiệu suất hệ thống. Trong các ứng dụng nhạy cảm với thời gian, một thuật toán mất quá nhiều thời gian để chạy có thể khiến kết quả của nó bị lỗi thời hoặc vô dụng. Một thuật toán không hiệu quả cũng có thể cần một lượng năng lượng tính toán hoặc lưu trữ không kinh tế để chạy, một lần nữa khiến nó thực sự vô dụng.

Các yếu tố không đổi

Phân tích các thuật toán thường tập trung vào hiệu suất tiệm cận, đặc biệt ở cấp sơ bộ, nhưng trong các ứng dụng thực tế, các yếu tố không đổi là quan trọng và trong thực tế, dữ liệu trong thực tế luôn bị giới hạn về kích thước. Giới hạn thường là kích thước của bộ nhớ có thể gắn địa chỉ, do đó, trên các máy 32 bit 2 ³² = 4 GiB (lớn hơn nếu sử dụng bộ nhớ được phân đoạn) và trên các máy ⁶⁴ bit 2 ⁶⁴ = 16 EiB. Do đó với một kích thước giới hạn, một thứ tự tăng trưởng (thời gian hoặc không gian) có thể được thay thế bằng một yếu tố không đổi và theo nghĩa này, tất cả các thuật toán thực tế là O (1) cho hằng số đủ lớn hoặc cho dữ liệu đủ nhỏ.
Giải thích này chủ yếu hữu ích cho các hàm phát triển cực kỳ chậm: logarit lặp (nhị phân) (log *) nhỏ hơn 5 cho tất cả dữ liệu thực tế (2 ⁶⁵⁵³⁶ bit); (nhị phân) log-log (log log n) nhỏ hơn 6 đối với hầu như tất cả dữ liệu thực tế (2 ⁶⁴ bit); và log nhị phân (log n) nhỏ hơn 64 đối với hầu như tất cả dữ liệu thực tế (2 ⁶⁴ bit). Tuy nhiên, thuật toán có độ phức tạp không liên tục có thể hiệu quả hơn thuật toán có độ phức tạp không đổi trên dữ liệu thực tế nếu chi phí của thuật toán thời gian không đổi dẫn đến hệ số hằng lớn hơn, ví dụ:     miễn là     và     Đối với các yếu tố tuyến tính hoặc bậc hai dữ liệu lớn không thể bị bỏ qua, nhưng đối với dữ liệu nhỏ, thuật toán không hiệu quả đôi khi có thể hiệu quả hơn. Điều này đặc biệt được sử dụng trong các thuật toán lai, như Timsort, sử dụng thuật toán hiệu quả bất đối xứng (ở đây là sắp xếp trộn, với độ phức tạp thời gian ), nhưng chuyển sang một thuật toán không hiệu quả không có triệu chứng (ở đây sắp xếp chèn, với độ phức tạp thời gian   ) cho dữ liệu nhỏ, vì thuật toán đơn giản nhanh hơn trên dữ liệu nhỏ.