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án | MÃ SỐ | Tại chỗ | ỔN ĐỊNH | TỐT NHẤT | TRUNG BÌNH | TỒI TỆ NHẤT | Nhậ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 case
| | sắ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 arrays
| | sắ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 instead
| | sắ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
subquadratic
| | N
| ¼ 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
stable
| | Chè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 practice
| | sắ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 place
| |
|
|
|
|
|
|
| Chèn.java |
N¼ N 2
| Sử dụng cho các mảng được sắp xếp bằng orpartally | MÃ SỐ | Sắp xếp bong bóng | DEL-MIN | Bong bóng.java | DEC-KEY | hiế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.javahiếm khi hữu ích; sử dụng loại chèn thay thế
|
|
| Vỏ đạn | Shell.java |
|---|
| Sử dụng cho các mảng được sắp xếp bằng orpartally | MÃ SỐ | Sắp xếp bong bóng | Sắp xếp bong bóng | hiếm khi hữu ích; sử dụng loại chèn thay thế | Sắp xếp bong bóng | Sắp xếp bong bóng | hiế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.java | Thuật toán | MÃ SỐ | n log3 n | khô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ÊN | Ký hiệu | SỰ 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ÊN | Ký hiệu | SỰ 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 call
| 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) | 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 tree
| 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) | \ (g (n) \) là \ (o (f (n)) \)
grade-school addition
BFPRT median finding
| 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) | \ (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 multiplication
| 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) | \ (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
- Giới hạn: & nbsp; If \ (\; \ DisplayStyle \ lim_ {n \ to \ infy} \ frac {f (n)} {g (n)} = 0 \), sau đó \ (f (n) \) (n)) \) nhưng không \ (\ theta (g (n)) \).
- Giới hạn: & nbsp; If \ (\; \ DisplayStyle \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = \ infy \), thì \ (f (n) \) là \ (\ Omega (g (n)) \) nhưng không \ (o (g (n)) \).
Dưới đây là một số ví dụ.
| HÀM SỐ | \ (o (n^2) \) | \ (O (n^2) \) | \ (\ Theta (n^2) \) | \ (\ Omega (n^2) \) | \ (\ omega (n^2) \) | \ (\ sim 2 n^2 \) | \ (\ sim 4 n^2 \) |
|---|
| \ (\ log_2 n \) | ✔ | ✔ |
|
|
|
|
| | \ (10n + 45 \) | ✔ | ✔ |
|
|
|
|
| | \ (10n + 45 \) |
| ✔ | ✔ | ✔ |
| ✔ |
| | \ (10n + 45 \) |
| ✔ | ✔ | ✔ |
|
| ✔ | | \ (10n + 45 \) |
|
|
| ✔ | ✔ |
|
| | \ (10n + 45 \) |
|
|
| ✔ | ✔ |
|
|
\ (10n + 45 \)\ (2n^2 + 45n + 12 \)
| \ (4n^2 - 2 \ sqrt {n} \) | \ (3n^3 \) | \ (2^n \) |
|---|
| Phân chia và chinh phục tái phát. | Đối với mỗi lần tái phát sau, chúng tôi giả sử \ (t (1) = 0 \) và rằng \ (n \,/\, 2 \) có nghĩa là \ (\ lfloor n \,/\, 2 \ rfloor \) hoặc \ (\ lceil n \,/\, 2 \ rceil \). | SỰ TÁI XUẤT | | \ (T (n) \) | THÍ DỤ | \ (T (n) = t (n \,/\, 2) + 1 \) | | \ (\ sim \ log_2 n \) | Tìm kiếm nhị phân | \ (T (n) = 2 t (n \,/\, 2) + n \) | | \ (\ sim n \ log_2 n \) | Mergesort | \ (T (n) = t (n-1) + n \) | | \ (\ sim \ frac {1} {2} n^2 \) | sắp xếp chèn | \ (T (n) = 2 t (n \,/\, 2) + 1 \) | | \ (\ sim n \) | Cây truyền tải | \ (T (n) = 2 t (n-1) + 1 \) | | \ (\ sim 2^n \) | Tháp của Hà Nội | \ (T (n) = 3 t (n \,/\, 2) + \ theta (n) \) | | \ (\ Theta (n^{\ log_2 3}) = \ theta (n^{1.58 ...}) \) | Nhân hóa Karatsuba | \ (T (n) = 7 t (n \,/\, 2) + \ theta (n^2) \) |
\ (\ Theta (n^{\ log_2 7}) = \ theta (n^{2.81 ...}) \)Phép nhân strassen - \ (T (n) = 2 t (n \,/\, 2) + \ theta (n \ log n) \)
- \ (\ Theta (n \ log^2 n) \)
- Cặp gần nhất
Định lý chủ. |
