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.^[1] 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:^[2]^[3]^[4]^[5]^[6]

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ể.^[7]

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:

n (kích thước danh sách)	Thời gian chạy ở máy A (tính bằng nano giây)	Thời gian chạy ở máy tính B (tính bằng nano giây)
16	8	100.000
63	32	150.000
250	125	200.000
1.000	500	250.000

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:

n (kích thước danh sách)	Thời gian chạy ở máy A (tính bằng nano giây)	Thời gian chạy ở máy tính B (tính bằng nano giây)
16	8	100.000
63	32	150.000
250	125	200.000
1.000	500	250.000
...	...	...
1.000.000	500.000	500.000
4.000.000	2.000.000	550.000
16.000.000	8.000.000	600.000
...	...	...
63,072 × 10 ¹²	31,536 × 10 ¹² ns, </br> hoặc 1 năm	1.375.000 ns, </br> hoặc 1,375 mili giây

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 $f(n)$ 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 $c\times f(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)$ .

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, $t \approx k n a$ , có thể tìm thấy hệ số a ^[8] 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=\log(t_{2}/t_{1})/\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:

n (kích thước danh sách)	Thời gian chạy của máy A (tính bằng nano giây)	Cấp độ địa phương của tăng trưởng (n ^ _)	Thời gian chạy máy tính B (tính bằng nano giây)	Cấp độ địa phương của tăng trưởng (n ^ _)
15	7		100.000
65	32	1,04	150.000	0,28
250	125	1,01	200.000	0,21
1.000	500	1,00	250.000	0,16
...	...		...
1.000.000	500.000	1,00	500.000	0,10
4.000.000	2.000.000	1,00	550.000	0,07
16.000.000	8.000.000	1,00	600.000	0,06
...	...		...

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.^[9] 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}.\,

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}+\cdots +(n-1)T_{6}+nT_{6}

có thể là yếu tố ^[10] như

T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\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ự:

{\begin{aligned}&2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}\\=\ &T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}\end{aligned}}

có thể được coi là

{\begin{aligned}&T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\=&T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}\\=&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}

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}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

làm giảm

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\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:

Prove that $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$

${\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}$

Let k be a constant greater than or equal to [T₁..T₇]

${\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}$

Therefore $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$

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:^[11]

$4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).$

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\log \log n$ miễn là $K/k>6$ và $n<2^{2^{6}}=2^{64}$ Đố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\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ỏ.

Xem thêm

Phân tích khấu hao
Phân tích các thuật toán song song
Độ phức tạp tính toán tiệm cận
Trường hợp tốt nhất, tồi tệ nhất và trung bình
Ký hiệu Big O
Lý thuyết phức tạp tính toán
Định lý tổng thể (phân tích thuật toán)
Hoàn thành NP
Phân tích số
Thời gian đa thức
Tối ưu hóa chương trình
Đo lường (lập trình máy tính)
Khả năng mở rộng
Phân tích mịn
Phân tích chấm dứt — dự án con của việc kiểm tra xem một chương trình sẽ chấm dứt hay không
Độ phức tạp thời gian - bao gồm bảng thứ tự tăng trưởng cho các thuật toán phổ biến
Sự phức tạp dựa trên thông tin

Ghi chú

^ “Knuth: Recent News”. web.archive.org. 28 tháng 8 năm 2016. Lưu trữ bản gốc ngày 28 tháng 8 năm 2016. Truy cập ngày 25 tháng 4 năm 2019.Quản lý CS1: bot: trạng thái URL ban đầu không rõ (liên kết)
^ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co., section 1.3
^ Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. tr. 177–178. ISBN 978-3-540-14015-3.
^ Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. tr. 3–8. ISBN 978-3-540-65431-5.
^ Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, tr. 20, ISBN 978-3-540-21045-0
^ Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. tr. 3–7. ISBN 978-0-89871-187-5.
^ Ví dụ về giá trừu tượng?, cstheory.stackexchange.com
^ Làm thế nào để tránh lạm dụng và hối lộ, tại blog "Thư bị mất của Gôdel và P = NP" của RJ Lipton, giáo sư khoa học máy tính tại Georgia Tech, kể lại ý tưởng của Robert Sedgewick
^ Tuy nhiên, đây không phải là trường hợp của một máy tính lượng tử
^ Nó có thể được chứng minh bằng cảm ứng rằng $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$
^ Cách tiếp cận này, không giống như các phương pháp trên, bỏ qua thời gian liên tục được tiêu thụ bởi các bài kiểm tra vòng lặp mà chấm dứt vòng tương ứng của họ, nhưng nó là tầm thường để chứng minh rằng thiếu sót như vậy không ảnh hưởng đến kết quả cuối cùng