Chúng tôi tóm tắt các đặc điểm hiệu suất của các thuật toán cổ điển và cấu trúc dữ liệu để sắp xếp, hàng đợi ưu tiên, bảng biểu tượng và xử lý đồ thị.
Chúng tôi cũng tóm tắt một số toán học hữu ích trong phân tích các thuật toán, bao gồm các chức năng thường gặp; công thức hữu ích và xấp xỉ; thuộc tính của logarit; ký hiệu tiệm cận; và các giải pháp để phân chia tái phát và chinh phục.
Sorting.
Bảng dưới đây tóm tắt số lượng so sánh cho một loạt các thuật toán sắp xếp, như được thực hiện trong sách giáo khoa này. Nó bao gồm các hằng số hàng đầu nhưng bỏ qua các điều khoản bậc thấp hơn.
Thuật toánMÃ SỐTại chỗỔN ĐỊNHTỐT NHẤTTRUNG BÌNHTỒI TỆ NHẤTNhận xét lựa chọn sắp xếp Lựa chọn.java ✔ ½ n 2 ½ n 2 ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
quadratic in best casesắp xếp chèn Chèn.java ✔ ✔ ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
partially-sorted arrayssắp xếp chèn Chèn.java ✔ ✔ ½ n 2 ½ n 2 ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
use insertion sort insteadsắp xếp chèn Chèn.java ✔ ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn Chèn.java
subquadraticN ¼ N 2 ✔ ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn
stableChèn.java N ✔ n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
fastest in practicesắp xếp chèn Chèn.java ✔ ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn
in placeChèn.java
N
¼ N 2
Sử dụng cho các mảng được sắp xếp bằng orpartallyMÃ SỐSắp xếp bong bóngDEL-MINBong bóng.javaDEC-KEYhiếm khi hữu ích; sử dụng loại chèn thay thếVỏ đạn Shell.java n log3 n 1 ½ n 2 ½ n 2 1 1 ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn Chèn.java Chèn.java 1 Chèn.java Chèn.java ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn Chèn.java N 1 Chèn.java N ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất sắp xếp chèn 1 Chèn.java 1 Chèn.java Chèn.java Chèn.java N ¼ N 2 1 Sử dụng cho các mảng được sắp xếp bằng orpartally 1 Sắp xếp bong bóng Sử dụng cho các mảng được sắp xếp bằng orpartally 1 Sắp xếp bong bóng
Bong bóng.java
hiếm khi hữu ích; sử dụng loại chèn thay thế
Vỏ đạnShell.java Sử dụng cho các mảng được sắp xếp bằng orpartallyMÃ SỐSắp xếp bong bóngSắp xếp bong bónghiếm khi hữu ích; sử dụng loại chèn thay thếSắp xếp bong bóngSắp xếp bong bónghiếm khi hữu ích; sử dụng loại chèn thay thế Vỏ đạn
(in an unordered list)Shell.java ½ n 2 ½ n 2 ½ n 2 ½ n 2 ½ n 2 ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
(in a sorted array)sắp xếp chèn Chèn.java ½ n 2 ½ n 2 Chèn.java ½ n 2 ½ n 2 n trao đổi; bậc hai trong trường hợp tốt nhất
(unbalanced)sắp xếp chèn ½ n 2 ½ n 2 ½ n 2 Chèn.java Chèn.java N ¼ N 2
(left-leaning)Sử dụng cho các mảng được sắp xếp bằng orpartally Chèn.java Chèn.java Chèn.java Chèn.java Chèn.java Chèn.java N
¼ N 2 Chèn.java Chèn.java Chèn.java Chèn.java Chèn.java Chèn.java N
(separate-chaining)¼ N 2 ½ n 2 ½ n 2 ½ n 2 Sắp xếp bong bóng Sắp xếp bong bóng Sắp xếp bong bóng Bong bóng.java
(linear-probing)hiếm khi hữu ích; sử dụng loại chèn thay thế ½ n 2 ½ n 2 ½ n 2 Sắp xếp bong bóng Sắp xếp bong bóng Sắp xếp bong bóng Bong bóng.java
hiếm khi hữu ích; sử dụng loại chèn thay thế
Vỏ đạn
Shell.javaThuật toánMÃ SỐn log3 nkhông xác định C N 3/2 Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java Hợp nhất.java ½ n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n Mã chặt chẽ; Mergesort Hợp nhất.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java Hợp nhất.java n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java ½ n lg n n lg n n log n đảm bảo; ổn định sắp xếp nhanh chóng Nhanh chóng.java 2 n ln n
n log n đảm bảo xác suất; nhanh nhất trong thực tế
Dưới đây là một số chức năng thường gặp khi phân tích các thuật toán.
HÀM SỐKý hiệuĐỊNH NGHĨA sàn nhà \ (\ lfloor x \ rfloor \) Số nguyên vĩ đại nhất \ (\; \ le \; x \) trần nhà \ (\ lceil x \ rceil \) Số nguyên nhỏ nhất \ (\; \ ge \; x \) Logarit nhị phân \ (\ lg x \) & nbsp; hoặc & nbsp; \ (\ log_2 x \) \ (y \) sao cho \ (2^{\, y} = x \) Logarit tự nhiên \ (\ ln x \) & nbsp; hoặc & nbsp; \ (\ log_e x \) \ (y \) sao cho \ (e^{\, y} = x \) Logarit chung \ (\ log_ {10} x \) \ (y \) sao cho \ (10^{\, y} = x \) logarit nhị phân lặp lại \ (\ lg^* x \) \ (0 \) nếu \ (x \ le 1; \; 1 + \ lg^*(\ lg x) \) số hài hòa \ (H_n \) \ (1 + 1/2 + 1/3 + \ ldots + 1/n \) yếu tố \( N! \) \ (1 \ lần 2 \ lần 3 \ lần \ ldots \ lần n \) hệ số nhị thức \ (n \ Chọn K \) \ (\ frac {n!} {k! \; (n-k)!} \)
Công thức hữu ích và xấp xỉ.
Dưới đây là một số công thức hữu ích cho các xấp xỉ được sử dụng rộng rãi trong phân tích các thuật toán.
- Summonic tổng: & nbsp; \ (1 + 1/2 + 1/3 + \ ldots + 1/n \ sim \ ln n \)
- Tổng hình tam giác: & nbsp; \ (1 + 2 + 3 + \ ldots + n = n \, (n + 1) \, / \, 2 \ sim n^2 \, / \, 2 \)
- Tổng hình vuông: & nbsp; \ (1^2 + 2^2 + 3^2 + \ ldots + n^2 \ sim n^3 \, / \, 3 \)
- Tổng hình học: & nbsp; If \ (r \ neq 1 \), thì \ (1 + r + r^2 + r^3 + \ ldots + r^n = (r^{n + 1} - 1) \; /\; (r - 1) \)
- \ (r = 1/2 \): & nbsp; \ (1 + 1/2 + 1/4 + 1/8 + \ ldots + 1/2^n \ sim 2 \)
- \ (r = 2 \): & nbsp; \ (1 + 2 + 4 + 8 + \ ldots + n/2 + n = 2n - 1 \ sim 2n \), khi \ (n \) là sức mạnh của 2
- Xấp xỉ của Stirling: & nbsp; \ (\ log_2 (n!) = \ log_2 1 + \ log_2 2 + \ log_2 3 + \ ldots + \ log_2 n \ sim n \ log_2 n \)
- Theo cấp số nhân: & nbsp; \ ((1 + 1/n)^n \ sim e; \; \; (1 - 1/n)^n \ sim 1/e \)
- Hệ số nhị thức: & nbsp; \ ({n \ chọn k} \ sim n^k \, / \, k! \) khi \ (k \) là một hằng số nhỏ
- Tổng hợp bằng tích phân: & nbsp; Nếu \ (f (x) \) là một hàm tăng đơn điệu, thì \ (\ DisplayStyle \ int_0^n f (x) \; dx \; \ le \; \ sum_ {i = 1}^n \; ) \; \ le \; \ int_1^{n+1} f (x) \; dx \)
Thuộc tính của logarit.
- Định nghĩa: & nbsp; \ (\ log_b a = c \) có nghĩa là \ (b^c = a \). Chúng tôi gọi \ (b \) là cơ sở của logarit.
- Các trường hợp đặc biệt: & NBSP; \ (\ log_b b = 1, \; \ log_b 1 = 0 \)
- Nghịch đảo của theo cấp số nhân: & nbsp; \ (b^{\ log_b x} = x \)
- Sản phẩm: & nbsp; \ (\ log_b (x \ lần y) = \ log_b x + \ log_b y \)
- Bộ phận: & NBSP; \ (\ log_b (x \ div y) = \ log_b x - \ log_b y \)
- Sản phẩm hữu hạn: & NBSP; \ (\ log_b (x_1 \ Times x_2 \ Times \ ldots \ Times x_n) \; = \;
- Thay đổi cơ sở: & nbsp; \ (\ log_b x = \ log_c x \; / \; \ log_c b \)
- Sắp xếp lại số mũ: & nbsp; \ (x^{\ log_b y} = y^{\ log_b x} \)
- Số mũ: & nbsp; \ (\ log_b (x^y) = y \ log_b x \)
Ký hiệu tiệm cận: Định nghĩa.
TÊNKý hiệuSỰ MÔ TẢĐỊNH NGHĨA Tilde \ (f (n) \ sim g (n) \; \) \ (f (n) \) bằng \ (g (n) \) không có triệu chứng (bao gồm các yếu tố không đổi)
(including constant factors)\ (\; \ DisplayStyle \ lim_ {n \ to \ infy} \ frac {f (n)} {g (n) OH lớn \ (f (n) \) là \ (o (g (n)) \) \ (f (n) \) được giới hạn ở trên bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi)
(ignoring constant factors)Có tồn tại các hằng số \ (c> 0 \) và \ (n_0 \ ge 0 \) sao cho \ (0 \ le f (n) \ le c \ cdot g (n) \) cho tất cả \ (n \ ge n_0 \ ) Omega lớn \ (f (n) \) là \ (\ omega (g (n)) \) \ (f (n) \) được giới hạn bên dưới bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi)
(ignoring constant factors)\ (g (n) \) là \ (o (f (n)) \) Theta lớn \ (f (n) \) là \ (\ theta (g (n)) \) \ (f (n) \) được giới hạn ở trên và dưới bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi)
(ignoring constant factors)\ (f (n) \) là cả \ (o (g (n)) \) và \ (\ omega (g (n)) \) Ồ ồ \ (f (n) \) là \ (o (g (n)) \) \ (f (n) \) bị chi phối bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi)
(ignoring constant factors)\ (\; \ DisplayStyle \ lim_ {n \ to \ infy} \ frac {f (n)} {g (n) Omega nhỏ \ (f (n) \) là \ (\ omega (g (n)) \) \ (f (n) \) thống trị \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi)
(ignoring constant factors)\ (g (n) \) là \ (o (f (n)) \)
Đơn đặt hàng chung của tăng trưởng.
TÊNKý hiệuSỰ MÔ TẢTilde \ (f (n) \ sim g (n) \; \) \ (f (n) \) bằng \ (g (n) \) không có triệu chứng (bao gồm các yếu tố không đổi) \ (\; \ DisplayStyle \ lim_ {n \ to \ infy} \ frac {f (n)} {g (n)
arithmetic operation
function callOH lớn \ (f (n) \) là \ (o (g (n)) \) \ (f (n) \) được giới hạn ở trên bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi) Có tồn tại các hằng số \ (c> 0 \) và \ (n_0 \ ge 0 \) sao cho \ (0 \ le f (n) \ le c \ cdot g (n) \) cho tất cả \ (n \ ge n_0 \ )
insert in a binary heap
search in a red–black treeOmega lớn \ (f (n) \) là \ (\ omega (g (n)) \) \ (f (n) \) được giới hạn bên dưới bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi) \ (g (n) \) là \ (o (f (n)) \)
grade-school addition
BFPRT median findingTheta lớn \ (f (n) \) là \ (\ theta (g (n)) \) \ (f (n) \) được giới hạn ở trên và dưới bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi) \ (f (n) \) là cả \ (o (g (n)) \) và \ (\ omega (g (n)) \)
heapsort
fast Fourier transformỒ ồ \ (f (n) \) là \ (o (g (n)) \) \ (f (n) \) bị chi phối bởi \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi) \ (\; \ DisplayStyle \ lim_ {n \ to \ infy} \ frac {f (n)} {g (n)
insertion sort
grade-school multiplicationOmega nhỏ \ (f (n) \) là \ (\ omega (g (n)) \) \ (f (n) \) thống trị \ (g (n) \) không có triệu chứng (bỏ qua các yếu tố không đổi) \ (g (n) \) là \ (o (f (n)) \)
Floyd–Warshall
grade-school matrix multiplicationĐơn đặt hàng chung của tăng trưởng. THÍ DỤ Mã mã Không thay đổi
AKS primality algorithm
Edmond's matching algorithm\ (O (1) \) Cuộc gọi hoạt động của AccessArithMetic op();
enumerating all permutations
backtracking search
Logarit
- \ (O (\ log n) \)
- Hằng số: & nbsp; If \ (f (n) \) là \ (o (g (n)) \) và \ (c> 0 \), thì \ (c \ cdot f (n) \) là \ (o (g (n ))) \).
- Sản phẩm: & nbsp; If \ (f_1 (n) \) là \ (o (g_1 (n)) \) và \ (f_2 (n) \) là \ (o (g_2 (n))) \), thì \ (f_1 (n ) \ cdot f_2 (n) \) là \ (o (g_1 (n) \ cdot g_2 (n))) \).
- Tổng: & nbsp; If \ (f_1 (n) \) là \ (o (g_1 (n)) \) và \ (f_2 (n) \) là \ (o (g_2 (n))) \), thì \ (f_1 (n ) + f_2 (n) \) là \ (o (\ max \ {g_1 (n), g_2 (n) \}) \).
- Tính chuyển tiếp: & nbsp; Nếu \ (f (n) \) là \ (o (g (n)) \) và \ (g (n) \) là \ (o (h (n)) \), thì \ (f (n) \) là \ (o (h (n)) \).
- Đa thức: & nbsp; Đặt \ (f (n) = a_0 + a_1 n + \ ldots + a_d n^d \) với \ (a_d> 0 \). Sau đó, \ (f (n) \) là \ (\ theta (n^d) \).
- Logarit và đa thức: & nbsp; \ (\ log_b n \) là \ (o (n^d) \) cho mỗi \ (b> 0 \) và mỗi \ (d> 0 \).
- Hàm mũ và đa thức: & nbsp; \ (n^d \) là \ (o (r^n) \) cho mỗi \ (r> 0 \) và mỗi \ (d> 0 \).
- Factorials: & nbsp; \ (n! \) là \ (2^{\ theta (n \ log n)} \).
- Giới hạn: & nbsp; If \ (\; \ DisplayStyle \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = c \) cho một số hằng số \ (0