Thuật toán đồ thị Cheat sheet pdf

Chúng tôi cũng tóm tắt một số toán học hữu ích trong việc phân tích các thuật toán, bao gồm các hàm thường gặp;

Sắp xếp

Bảng dưới đây tóm tắt số lần so sánh cho nhiều thuật toán sắp xếp khác nhau, như được triển khai trong sách giáo khoa này. Nó bao gồm các hằng số đứng đầu nhưng bỏ qua các số hạng bậc thấp hơn

ALGORITHMCODEIN PLACESTABLEBESTAVERAGEWORSTREMARKSsắp xếp lựa chọnLựa chọn. java✔½ n 2½ n 2½ n 2n trao đổi;
bậc hai trong trường hợp tốt nhấtchèn sắp xếpChèn. java✔✔n¼ n 2½ n 2sử dụng cho mảng nhỏ hoặc
mảng được sắp xếp một phầnbubble sortBubble. java✔✔n½ n 2½ n 2hiếm khi hữu ích;
sử dụng sắp xếp chèn thay vì shellsortShell. java✔n log3 nunknownc n 3/2mã chặt chẽ;
subquadraticmergesortMerge. java✔½ n lg nn lg nn lg nn log n đảm bảo;
stablequicksortQuick. java✔n lg n2 n ln n½ n 2n log n đảm bảo xác suất;
nhanh nhất trong thực tếheapsortHeap. java✔n †2 n lg n2 n lg nn log n đảm bảo;
tại chỗ† \(n \log_2 n\) nếu tất cả các khóa khác nhau

hàng đợi ưu tiên

Bảng dưới đây tóm tắt thứ tự tăng trưởng thời gian chạy của các thao tác đối với nhiều hàng đợi ưu tiên khác nhau, như được triển khai trong sách giáo khoa này. Nó bỏ qua các hằng số hàng đầu và các điều khoản bậc thấp hơn. Ngoại trừ như đã lưu ý, tất cả thời gian chạy là thời gian chạy trong trường hợp xấu nhất

bảng ký hiệu

Bảng dưới đây tóm tắt thứ tự tăng thời gian chạy của các hoạt động cho nhiều bảng biểu tượng, như được thực hiện trong sách giáo khoa này. Nó bỏ qua các hằng số hàng đầu và các điều khoản bậc thấp hơn

xử lý đồ thị

Bảng dưới đây tóm tắt thứ tự tăng trưởng của thời gian chạy và mức sử dụng bộ nhớ trong trường hợp xấu nhất (ngoài bộ nhớ dành cho chính biểu đồ) đối với nhiều vấn đề xử lý biểu đồ, như được triển khai trong sách giáo khoa này. Nó bỏ qua các hằng số hàng đầu và các điều khoản bậc thấp hơn. Tất cả thời gian chạy là thời gian chạy trong trường hợp xấu nhất

Các chức năng thường gặp

Dưới đây là một số hàm thường gặp khi phân tích thuật toán

FUNCTIONNOTATIONDEFINITIONfloor\( \lfloor x \rfloor \)số nguyên lớn nhất \(\; \le \; x\)ceiling\( \lceil x \rceil \)số nguyên nhỏ nhất \(\; \ge \; x\)logarit nhị phân\( . \)\(1 \times 2 \times 3 \times \ldots \times n\)hệ số nhị thức\( n \choose k \)\( \frac{n. {k. \; . }\)

Các công thức và xấp xỉ hữu ích

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

• tổng hài hòa. \(1 + 1/2 + 1/3 + \ldots + 1/n \sim \ln n\)
• tổng tam giác. \(1 + 2 + 3 + \ldots + n = n \, (n+1) \, / \, 2 \sim n^2 \,/\, 2\)
• Tổng bình phương. \(1^2 + 2^2 + 3^2 + \ldots + n^2 \sim n^3 \, / \, 3\)
• tổng hình học. Nếu \(r \neq 1\), thì \(1 + r + r^2 + r^3 + \ldots + r^n = (r^{n+1} - 1) \; /\; (r
  • \(r = 1/2\). \(1 + 1/2 + 1/4 + 1/8 + \ldots + 1/2^n \sim 2\)
  • \(r = 2\). \(1 + 2 + 4 + 8 + \ldots + n/2 + n = 2n - 1 \sim 2n\), khi \(n\) là lũy thừa của 2
• Xấp xỉ Stirling. \(\log_2 (n. ) = \log_2 1 + \log_2 2 + \log_2 3 + \ldots + \log_2 n \sim n \log_2 n\)
• số mũ. \((1 + 1/n)^n \sim e; \;\;(1 - 1/n)^n \sim 1 / e\)
• hệ số nhị thức. \({n \choose k} \sim n^k \, / \, k. \) khi \(k\) là một hằng số nhỏ
• Tổng gần đúng bằng tích phân. Nếu \(f(x)\) là hàm đơn điệu tăng thì \( \displaystyle \int_0^n f(x) \; dx \; \le \; \sum_{i=1}^n \; f(i

Tính chất của logarit

• Sự định nghĩa. \(\log_b a = c\) nghĩa là \(b^c = a\). Chúng tôi coi \(b\) là cơ số của logarit
• trường hợp đặc biệt. \(\log_b b = 1,\; \log_b 1 = 0 \)
• Nghịch đảo của cấp số nhân. \(b^{\log_b x} = x\)
• Sản phẩm. \(\log_b (x \times y) = \log_b x + \log_b y \)
• Phân công. \(\log_b (x \div y) = \log_b x - \log_b y \)
• Sản phẩm hữu hạn. \(\log_b ( x_1 \times x_2 \times \ldots \times x_n) \; = \; \log_b x_1 + \log_b x_2 + \ldots + \log_b x_n\)
• Thay đổi căn cứ. \(\log_b x = \log_b a \; / \; \log_c b \)
• Sắp xếp lại số mũ. \(x^{\log_b y} = y^{\log_b x}\)
• lũy thừa. \(\log_b (x^y) = y \log_b x \)

ký hiệu tiệm cận. các định nghĩa

NAMENOTATIONDESCRIPTIONDEFINITIONTilde\(f(n) \sim g(n)\; \)\(f(n)\) bằng \(g(n)\) tiệm cận(including constant factors)\( \; \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1\)Big Oh\(f(n)\) is \(O(g(n))\)\(f(n)\) is bounded above by \(g(n)\) asymptotically
(ignoring constant factors)there exist constants \(c > 0\) and \(n_0 \ge 0\) such that \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\)Big Omega\(f(n)\) is \(\Omega(g(n))\)\(f(n)\) is bounded below by \(g(n)\) asymptotically
(ignoring constant factors)\( g(n) \) is \(O(f(n))\)Big Theta\(f(n)\) is \(\Theta(g(n))\)\(f(n)\) is bounded above and below by \(g(n)\) asymptotically
(ignoring constant factors)\( f(n) \) is both \(O(g(n))\) and \(\Omega(g(n))\)Little oh\(f(n)\) is \(o(g(n))\)\(f(n)\) is dominated by \(g(n)\) asymptotically
(ignoring constant factors)\( \; \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\)Little omega\(f(n)\) is \(\omega(g(n))\)\(f(n)\) dominates \(g(n)\) asymptotically
(ignoring constant factors)\( g(n) \) is \(o(f(n))\)

Thứ tự tăng trưởng chung

NAMENOTATIONEXAMPLECODE FRAGMENTTruy cập mảng hằng\(O(1)\)
phép toán số học
gọi hàm

op();

Logarit\(O(\log n)\)nhị phân
insert in a binary heap
search in a red–black tree

for (int i = 1; i <= n; i = 2*i)
   op();

Linear\(O(n)\)sequential search
grade-school addition
BFPRT median finding

for (int i = 0; i < n; i++)
   op();

Linearithmic\(O(n \log n)\)mergesort
heapsort
fast Fourier transform

for (int i = 1; i <= n; i++)
   for (int j = i; j <= n; j = 2*j)
      op();

Quadratic\(O(n^2)\)enumerate all pairs
insertion sort
grade-school multiplication

for (int i = 0; i < n; i++)
   for (int j = i+1; j < n; j++)
      op();

Cubic\(O(n^3)\)enumerate all triples
Floyd–Warshall
grade-school matrix multiplication

for (int i = 0; i < n; i++)
   for (int j = i+1; j < n; j++)
      for (int k = j+1; k < n; k++)
         op();

Polynomial\(O(n^c)\)ellipsoid algorithm for LP
AKS primality algorithm
Edmond's matching algorithmExponential\(2^{O(n^c)}\)enumerating all subsets
enumerating all permutations
backtracking search

ký hiệu tiệm cận. tính chất

• phản xạ. \(f(n)\) là \(O(f(n))\)
• hằng số. Nếu \(f(n)\) là \(O(g(n))\) và \( c > 0 \), thì \(c \cdot f(n)\) là \(O(g(n)
• Các sản phẩm. Nếu \(f_1(n)\) là \(O(g_1(n))\) và \( f_2(n) \) là \(O(g_2(n)))\), thì \(f_1(n
• mặt trời. Nếu \(f_1(n)\) là \(O(g_1(n))\) và \( f_2(n) \) là \(O(g_2(n)))\), thì \(f_1(n
• chuyển tiếp. Nếu \(f(n)\) là \(O(g(n))\) và \( g(n) \) là \(O(h(n))\), thì \( f(n)
• đa thức. Đặ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. \( \log_b n \) là \(O(n^d)\) cho mọi \( b > 0\) và mọi \( d > 0 \)
• Hàm mũ và đa thức. \( n^d \) là \(O(r^n)\) với mọi \( r > 0\) và mọi \( d > 0 \)
• giai thừa. \( N. \) là \( 2^{\Theta(n \log n)} \)
• Hạn mức. Nếu \( \; \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = c\) đối với hằng số \( 0 < c < \infty\), thì \
• Hạn mức. Nếu \( \; \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\), thì \(f(n)\) là \(O(g
• Hạn mức. Nếu \( \; \displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\), thì \(f(n)\) là \(\Omega

Dưới đây là một số ví dụ

FUNCTION\(o(n^2)\)\(O(n^2)\)\(\Theta(n^2)\)\(\Omega(n^2)\)\(\omega(n^

Định kỳ chia để trị

Đối với mỗi lần lặp lại sau, chúng tôi giả sử \(T(1) = 0\) và \(n\,/\,2\) có nghĩa là \(\lfloor n\,/\,2 \rfloor\) hoặc \

RECURRENCE\(T(n)\)VÍ DỤ\(T(n) = T(n\,/\,2) + 1\)\(\sim \log_2 n\)tìm kiếm nhị phân\(T(n) = 2 . 58. })\)Karatsuba phép nhân\(T(n) = 7 T(n\,/\,2) + \Theta(n^2)\)\(\Theta(n^{\log_2 7}) = \Theta . 81. })\)Phép nhân Strassen\(T(n) = 2 T(n\,/\,2) + \Theta(n \log n)\)\(\Theta(n \log^2 n)\)gần nhất

định lý tổng thể

Đặt \(a \ge 1\), \(b \ge 2\), và \(c > 0\) và giả sử rằng \(T(n)\) là một hàm trên các số nguyên không âm thỏa mãn

• Nếu \(c < \log_b a\), thì \(T(n) = \Theta(n^{\log_{\,b} a})\)
• Nếu \(c = \log_b a\), thì \(T(n) = \Theta(n^c \log n)\)
• Nếu \(c > \log_b a\), thì \(T(n) = \Theta(n^c)\)

Nhận xét. có nhiều phiên bản khác nhau của định lý tổng thể. Định lý Akra–Bazzi là một trong những định lý mạnh mẽ nhất