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

nhỏ| Để tìm kiếm một mục đã cho trong một danh sách theo thứ tự nhất định, có thể sử dụng cả thuật toán [[Tìm kiếm tuần tự|tìm kiếm nhị phân và tuyến tính (bỏ qua thứ tự). Phân tích của thuật toán trước và thuật toán sau cho thấy rằng phải mất tối đa các bước kiểm tra log ₂ (n) và n tương ứng cho một danh sách có độ dài n. Trong danh sách ví dụ được mô tả có độ dài 33, tìm kiếm "Morin, Arthur" lần lượt thực hiện 5 và 28 bước với tìm kiếm nhị phân (hiển thị bằng màu lam ) và tìm kiếm tuyến tính (màu tím ). ]] nhỏ|Đồ thị của các hàm thường được sử dụng trong phân tích thuật toán, hiển thị số lượng hoạt động N so với kích thước đầu vào n cho mỗi chức năng 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ả.

Mô hình chi phí

Ước tính hiệu quả thời gian phụ thuộc vào những gì chúng ta xác định là một bước. Để phân tích tương ứng hữu ích với thời gian thực hiện thực tế, thời gian cần thiết để thực hiện một bước phải được đảm bảo giới hạn ở trên bởi một hằng số. Cái phải quan tâm ở đây; chẳng hạn, một số phân tích tính phép cộng hai số là một bước. Giả định này có thể không được đảm bảo trong các bối cảnh nhất định. Ví dụ: nếu các số liên quan đến tính toán có thể lớn tùy ý, thời gian cần thiết cho một phép cộng không còn có thể được coi là không đổi.

Hai mô hình chi phí thường được sử dụng:

• mô hình chi phí thống nhất, còn được gọi là đo lường chi phí thống nhất (và các biến thể tương tự), gán một chi phí không đổi cho mọi hoạt động của máy, bất kể kích thước của các con số liên quan
• mô hình chi phí logarit, còn được gọi là đo lường chi phí logarit (và các biến thể tương tự), gán chi phí cho mọi hoạt động của máy tỷ lệ thuận với số bit liên quan

Cái sau thì khó sử dụng hơn, vì vậy nó chỉ được sử dụng khi cần thiết, ví dụ như trong phân tích các thuật toán số học độ dài tùy ý, giống như các thuật toán được sử dụng trong mật mã.

Một điểm quan trọng thường bị bỏ qua là các giới hạn thấp hơn được công bố cho các vấn đề, thường được đưa ra cho một mô hình tính toán bị ràng buộc nhiều hơn so với tập hợp các hoạt động mà bạn có thể sử dụng trong thực tế và do đó có các thuật toán nhanh hơn những gì bạn nghĩa là có thể.

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.

Những thiếu sót của số liệu thực nghiệm

Do các thuật toán độc lập với nền tảng (nghĩa là một thuật toán nhất định có thể được thực hiện bằng ngôn ngữ lập trình tùy ý trên một máy tính tùy ý chạy hệ điều hành tùy ý), có một số hạn chế đáng kể khi sử dụng phương pháp thực nghiệm để đánh giá hiệu năng so sánh của một tập hợp thuật toán.

Lấy ví dụ một chương trình tìm kiếm một mục cụ thể trong danh sách được sắp xếp có kích thước n. Giả sử chương trình này được triển khai trên Máy tính A, một máy hiện đại, sử dụng thuật toán tìm kiếm tuần tự và trên Máy tính B, một máy chậm hơn nhiều, sử dụng thuật toán tìm kiếm nhị phân. Kiểm tra điểm chuẩn trên hai máy tính chạy chương trình tương ứng của chúng có thể trông giống như sau:

Dựa trên các số liệu này, có thể dễ dàng đi đến kết luận rằng Máy tính A đang chạy một thuật toán có hiệu quả vượt trội so với Máy tính B. Tuy nhiên, nếu kích thước của danh sách đầu vào được tăng lên đủ lớn, kết luận đó được chứng minh là sai:

Máy tính A, chạy chương trình tìm kiếm tuần tự, thể hiện tốc độ tăng trưởng tuyến tính. Thời gian chạy của chương trình tỷ lệ thuận với kích thước đầu vào của nó. Nhân đôi kích thước đầu vào nhân đôi thời gian chạy, tăng gấp bốn lần kích thước đầu vào tăng gấp bốn lần thời gian chạy, v.v. Mặt khác, Computer B, chạy chương trình tìm kiếm nhị phân, thể hiện tốc độ tăng trưởng logarit. Tăng gấp bốn lần kích thước đầu vào chỉ làm tăng thời gian chạy thêm một lượng không đổi (trong ví dụ này là 50.000 ns). Mặc dù Máy tính A rõ ràng là một máy nhanh hơn, Máy tính B chắc chắn sẽ vượt qua Máy tính A trong thời gian chạy vì nó chạy một thuật toán với tốc độ tăng trưởng chậm hơn nhiều.

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à .

Cấp độ tăng trưởng theo kinh nghiệm

Giả sử thời gian thực hiện theo quy tắc công suất, __, có thể tìm thấy hệ số a bằng cách thực hiện các phép đo thực nghiệm về thời gian chạy $\{t\_1,\; t\_2\}$ tại một số điểm kích thước vấn đề $\{n\_1,\; n\_2\}$ và tính toán $t\_2/t\_1\; =\; (n\_2/n\_1)^a$ vậy $a\; =\; \backslash log(t\_2/t\_1)\; /\; \backslash log(n\_2/n\_1)$. Nói cách khác, điều này đo độ dốc của đường thực nghiệm trên biểu đồ log log của thời gian thực hiện so với kích thước bài toán, tại một số điểm kích thước. Nếu thứ tự tăng trưởng thực sự tuân theo quy tắc sức mạnh (và do đó, đường trên log log log thực sự là một đường thẳng), giá trị thực nghiệm của a sẽ không đổi ở các phạm vi khác nhau, và nếu không, nó sẽ thay đổi (và đường là một đường cong) - nhưng vẫn có thể phục vụ cho việc so sánh bất kỳ hai thuật toán đã cho nào về các cấp độ hành vi tăng trưởng theo kinh nghiệm của chúng. Áp dụng cho bảng trên:

Rõ ràng là thuật toán đầu tiên thể hiện một trật tự tăng trưởng tuyến tính thực sự tuân theo quy tắc sức mạnh. Các giá trị thực nghiệm cho cái thứ hai đang giảm đi nhanh chóng, cho thấy nó tuân theo một quy luật tăng trưởng khác và trong mọi trường hợp có thứ tự tăng trưởng địa phương thấp hơn nhiều (và cải thiện hơn nữa), theo kinh nghiệm, so với cái đầu tiên.

Đánh giá độ phức tạp thời gian chạy

Độ phức tạp thời gian chạy cho kịch bản trường hợp xấu nhất của thuật toán đã cho đôi khi có thể được đánh giá bằng cách kiểm tra cấu trúc của thuật toán và đưa ra một số giả định đơn giản hóa. Hãy xem xét các mã giả sau đây: 1 get a positive integer from input 2 if n > 10 3 print "Việc này có thể mất 1 lúc..." 4 for i = 1 to n 5 for j = 1 to i 6 print i * j 7 print "Xong!" Một máy tính nhất định sẽ mất một lượng thời gian riêng biệt để thực hiện từng hướng dẫn liên quan đến việc thực hiện thuật toán này. Lượng thời gian cụ thể để thực hiện một lệnh đã cho sẽ khác nhau tùy thuộc vào lệnh nào được thực thi và máy tính nào đang thực hiện lệnh đó, nhưng trên máy tính thông thường, lượng này sẽ mang tính quyết định. Giả sử các hành động được thực hiện trong bước 1 được coi là tiêu tốn thời gian T ₁, bước 2 sử dụng thời gian T ₂, v.v.

Trong thuật toán trên, các bước 1, 2 và 7 sẽ chỉ được chạy một lần. Đối với đánh giá trường hợp xấu nhất, cần giả định rằng bước 3 cũng sẽ được chạy. Do đó, tổng thời gian để chạy các bước 1-3 và bước 7 là:

:$$ $T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7.\; \backslash ,$

Các vòng lặp trong các bước 4, 5 và 6 là khó khăn hơn để đánh giá. Kiểm tra vòng lặp bên ngoài trong bước 4 sẽ thực hiện (n + 1) lần (lưu ý rằng cần thêm một bước để chấm dứt vòng lặp for, do đó n + 1 chứ không phải n thực thi), sẽ tiêu tốn thời gian T ₄ (n + 1). Mặt khác, vòng lặp bên trong được điều chỉnh bởi giá trị của j, lặp từ 1 đến i. Trong lần đầu tiên đi qua vòng ngoài, j lặp từ 1 đến 1: Vòng lặp bên trong tạo một lượt, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn thời gian T ₆ và kiểm tra vòng lặp bên trong (bước 5) tiêu tốn 2 T ₅ lần. Trong lần truyền tiếp theo qua vòng ngoài, j lặp từ 1 đến 2: vòng trong tạo ra hai lần, do đó, việc chạy thân vòng trong (bước 6) tiêu tốn 2 T ₆ thời gian và kiểm tra vòng trong (bước 5) tiêu tốn 3 T ₅ lần.

Nhìn chung, tổng thời gian cần thiết để chạy phần thân vòng trong có thể được biểu diễn dưới dạng một tiến trình số học:

: $T\_6\; +\; 2T\_6\; +\; 3T\_6\; +\; \backslash cdots\; +\; (n-1)\; T\_6\; +\; n\; T\_6$

có thể là yếu tố như

: $T\_6\; \backslash left[\; 1\; +\; 2\; +\; 3\; +\; \backslash cdots\; +\; (n-1)\; +\; n\; \backslash right]\; =\; T\_6\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]$

Tổng thời gian cần thiết để chạy thử nghiệm vòng lặp bên ngoài có thể được đánh giá tương tự:

:

có thể được coi là

:

Do đó, tổng thời gian chạy cho thuật toán này là:

:$f(n)\; =\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7\; +\; (n\; +\; 1)T\_4\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2+3n)\; \backslash right]\; T\_5$

làm giảm

:$f(n)\; =\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; n)\; \backslash right]\; T\_6\; +\; \backslash left[\; \backslash frac\{1\}\{2\}\; (n^2\; +\; 3n)\; \backslash right]\; T\_5\; +\; (n\; +\; 1)T\_4\; +\; T\_1\; +\; T\_2\; +\; T\_3\; +\; T\_7$

Theo nguyên tắc thông thường, người ta có thể giả định rằng thành phần bậc cao nhất trong bất kỳ hàm đã cho nào chi phối tốc độ tăng trưởng của nó và do đó xác định thứ tự thời gian chạy của nó. Trong ví dụ này, n ² là số hạng bậc cao nhất, vì vậy người ta có thể kết luận rằng f (n) = O (n ²). Chính thức điều này có thể được chứng minh như sau: Một cách tiếp cận thanh lịch hơn để phân tích thuật toán này sẽ là tuyên bố rằng [ T ₁.. T ₇ ] đều bằng một đơn vị thời gian, trong một hệ thống các đơn vị được chọn sao cho một đơn vị lớn hơn hoặc bằng thời gian thực tế cho các bước này. Điều này có nghĩa là thời gian chạy của thuật toán bị hỏng như sau:

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ụ với 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ụ: $K\; >\; k\; \backslash log\; \backslash log\; n$ miễn là $K/k\; >\; 6$ 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 $n\; \backslash log\; n$), 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 $n^2$) cho dữ liệu nhỏ, vì thuật toán đơn giản nhanh hơn trên dữ liệu nhỏ.