1.5. Phân tích tiệm cận: Ký hiệu Big-O và nhiều hơn nữa
Hiệu quả của một thuật toán phụ thuộc vào lượng thời gian, lưu trữ và các tài nguyên khác cần thiết để thực hiện thuật toán. Hiệu quả được đo lường bằng cách sử dụng ký hiệu tiệm cận.
Một thuật toán có thể không có cùng hiệu suất đối với các loại đầu vào khác nhau. Khi kích thước đầu vào tăng lên, hiệu suất sẽ thay đổi.
Nghiên cứu về sự thay đổi hiệu suất của thuật toán khi thứ tự kích thước đầu vào thay đổi được định nghĩa là phân tích tiệm cận.
1.5.1. Ký hiệu tiệm cận
Ký hiệu tiệm cận là ký hiệu toán học được sử dụng để mô tả thời gian chạy của một thuật toán khi đầu vào có xu hướng hướng tới một giá trị cụ thể hoặc một giá trị giới hạn.
Ví dụ: Trong sắp xếp nổi bọt, khi mảng đầu vào đã được sắp xếp, thời gian mà thuật toán thực hiện là tuyến tính tức là trường hợp tốt nhất.
Nhưng khi mảng đầu vào ở trạng thái đảo ngược, thuật toán sẽ mất thời gian tối đa (bậc hai) để sắp xếp các phần tử tức là trường hợp xấu nhất.
Khi mảng đầu vào không được sắp xếp hoặc theo thứ tự ngược lại, thì mất thời gian trung bình. Các khoảng thời gian này được biểu thị bằng ký hiệu tiệm cận.
Chủ yếu có ba ký hiệu tiệm cận:
-Ký hiệu Big-O
-Ký hiệu Omega
-Ký hiệu Theta
a. Ký hiệu Big-O (ký hiệu O)
Ký hiệu Big-O biểu diễn giới hạn trên của thời gian chạy của một thuật toán. Do đó, nó đưa ra độ phức tạp trường hợp xấu nhất của một thuật toán.
Big-O đưa ra giới hạn trên của một hàm
O(g(n)) = { f(n): tồn tại các hằng số dương c và \(n_{0}\) sao cho 0 ≤ f(n) ≤ cg(n) với mọi n ≥ \(n_{0}\) }
Biểu thức trên có thể được mô tả như một hàm f(n) thuộc tập O(g(n)) nếu tồn tại một hằng số dương c sao cho nó nằm giữa 0 và cg(n), với n đủ lớn.
Với bất kỳ giá trị n nào, thời gian chạy của một thuật toán không vượt qua thời gian do O(g(n)) cung cấp.
Vì nó cung cấp thời gian chạy trường hợp xấu nhất của một thuật toán, nên nó được sử dụng rộng rãi để phân tích một thuật toán vì chúng ta luôn quan tâm đến trường hợp xấu nhất.
b. Ký hiệu Omega (ký hiệu Ω)
Ký hiệu Omega biểu thị giới hạn dưới của thời gian chạy của một thuật toán. Do đó, nó cung cấp độ phức tạp trường hợp tốt nhất của một thuật toán.
Omega đưa ra giới hạn dưới của một hàm
Ω(g(n)) = { f(n): tồn tại hằng số dương c và \(n_{0}\) sao cho 0 ≤ cg(n) ≤ f(n) với mọi n ≥ \(n_{0}\) }
Biểu thức trên có thể được mô tả như một hàm f(n) thuộc tập Ω(g(n)) nếu tồn tại một hằng số dương c sao cho nó nằm trên cg(n), với n đủ lớn.
Đối với bất kỳ giá trị n nào, thời gian tối thiểu mà thuật toán yêu cầu được đưa ra bởi Omega Ω(g(n)).
c.Ký hiệu Theta (ký hiệu Θ)
Ký hiệu Theta bao quanh hàm từ trên xuống dưới. Vì nó biểu diễn giới hạn trên và giới hạn dưới của thời gian chạy của một thuật toán, nên nó được sử dụng để phân tích độ phức tạp trường hợp trung bình của một thuật toán.
Theta giới hạn hàm trong các hằng số
Đối với hàm g(n), Θ(g(n)) được đưa ra bởi mối quan hệ:
Θ(g(n)) = { f(n): tồn tại các hằng số dương \(c_ {1}\), \(c_ {2}\) và \(n_ {0}\) Sao cho 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) với mọi n ≥ \(n_ {0}\) }
Biểu thức trên có thể được mô tả như một hàm f(n) thuộc tập Θ(g(n)) nếu tồn tại các hằng số dương \(c_{1}\) và \(c_{2}\) sao cho nó có thể được kẹp giữa \(c_{1}\) g(n) và \(c_{2}\) g(n), với n đủ lớn.
Nếu một hàm f(n) nằm ở bất kỳ vị trí nào giữa \(c_{1}\) g(n) và \(c_{2}\) g(n) với mọi n ≥ n0, thì f(n) được gọi là liên kết chặt tiệm cận.
1.6. Định lý tổng quát
Phương pháp chính là công thức giải phương trình hồi quy có dạng:
T(n) = aT(n/b) + f(n), Trong đó, n = kích thước đầu vào a = số lượng bài toán con trong đệ quy n/b = kích thước của mỗi bài toán con. Tất cả các bài toán con đều được giả định. f(n) = chi phí của công việc được thực hiện bên ngoài lệnh gọi đệ quy, bao gồm chi phí chia nhỏ vấn đề và chi phí hợp nhất các giải pháp Tại đây, a ≥ 1 và b > 1 là các hằng số và f(n) là hàm dương tiệm cận.
Một hàm dương tiệm cận có nghĩa là đối với giá trị n đủ lớn, chúng ta có f(n) > 0.
Định lý tổng quát
Nếu a ≥ 1 và b > 1 là hằng số và f(n) là hàm dương tiệm cận, thì độ phức tạp thời gian của một quan hệ đệ quy được đưa ra bởi:
T(n) = aT(n/b) + f(n)
trong đó, T(n) có các giới hạn tiệm cận sau:
1. If f(n) = O(\(n^{\log_{b}^{a}-\epsilon}\)), then T(n) = Θ(\(n^{\log_{b}^{a}}\)).
2. If f(n) = Θ(\(n^{\log_{b}^{a}}\)), then T(n) = Θ(\(n^{\log_{b}^{a}}\) * log n).
3. If f(n) = Ω(\(n^{\log_{b}^{a}+\epsilon}\)), then T(n) = Θ(f(n)).
ϵ > 0 là một hằng số.
Mỗi điều kiện trên có thể được hiểu như sau:
1.Nếu chi phí giải quyết các bài toán con ở mỗi cấp độ tăng lên theo một hệ số nhất định, giá trị của f(n) sẽ trở nên nhỏ hơn theo đa thức so với \(n^{\log_{b}^{a}}\) . Do đó, độ phức tạp về thời gian bị áp đảo bởi chi phí của cấp độ cuối cùng tức là ie. \(n^{\log_{b}^{a}}\).
2.Nếu chi phí giải quyết tiểu vấn đề ở mỗi cấp độ gần bằng nhau thì giá trị của f(n) sẽ là \(n^{\log_{b}^{a}}\). Do đó, độ phức tạp về thời gian sẽ là f(n) lần tổng số cấp độ ie. \(n^{\log_{b}^{a}}\). * log n
3.Nếu chi phí giải quyết các bài toán con ở mỗi cấp độ giảm đi một hệ số nhất định, giá trị của f(n) sẽ trở nên lớn hơn theo đa thức so với \(n^{\log_{b}^{a}}\) . Do đó, độ phức tạp về thời gian bị ảnh hưởng bởi chi phí của f(n).
1.6.1. Ví dụ đã giải của Định lý tổng quát
T(n) = 3T(n/2) + \(n^2\) Ở đây, a = 3 n/b = n/2 f(n) = n2
\(log_{b}^{a}\) = \(log_{2}^{3}\) ≈ 1.58 < 2
ie. f(n) > \(n^{\log_{b}^{a+\epsilon}}\) , trong đó, ϵ là một hằng số.
Case 3 ngụ ý ở đây.
Do đó, T(n) = f(n) = Θ(\(n^2\))
1.6.2.Giới hạn của định lý tổng quát
Định lý tổng quát không thể được sử dụng nếu:
T(n)không phải là đơn điệu. Ví dụ. T(n) = sin n
f(n) không phải là đa thức. Ví dụ. f(n) = \(2^n\)
a không phải là hằng số. Ví dụ. a = 2n
a < 1
1.7.Thuật toán chia để trị
Thuật toán chia để trị là một chiến lược giải quyết một vấn đề lớn bằng cách
chia nhỏ vấn đề thành các bài toán con nhỏ hơn
giải quyết các bài toán con và
kết hợp chúng để có được kết quả mong muốn.
Để sử dụng thuật toán chia để trị, đệ quy được sử dụng. Tìm hiểu về đệ quy trong các ngôn ngữ lập trình khác nhau:
Đệ quy trong Java
Đệ quy trong Python
Đệ quy trong C++
1.7.1.Thuật toán chia để trị hoạt động như thế nào?
Sau đây là các bước liên quan:
Chia: Chia bài toán đã cho thành các bài toán con bằng cách đệ quy.
Chinh phục: Giải các bài toán con nhỏ hơn theo cách đệ quy. Nếu bài toán con đủ nhỏ, hãy giải trực tiếp.
Kết hợp: Kết hợp các giải pháp của các bài toán con là một phần của quá trình đệ quy để giải quyết bài toán thực tế.
Hãy cùng tìm hiểu khái niệm này thông qua một ví dụ.
Ở đây, chúng ta sẽ sắp xếp một mảng bằng cách sử dụng phương pháp chia để trị (tức là sắp xếp hợp nhất).
a.Hãy để mảng đã cho là
Mảng để sắp xếp hợp nhất
b.Chia mảng thành hai nửa.
Chia mảng thành hai phần nhỏ
Một lần nữa, chia từng phần theo cách đệ quy thành hai nửa cho đến khi bạn có được các phần tử riêng lẻ.
Chia mảng thành các phần nhỏ hơn
c.Bây giờ, kết hợp các yếu tố riêng lẻ theo cách có sắp xếp. Ở đây, các bước chinh phục và kết hợp diễn ra song song.
Kết hợp các phần phụ
1.7.2.Độ phức tạp thời gian
Độ phức tạp của thuật toán chia để trị được tính toán bằng định lý tổng quát.
T(n) = aT(n/b) + f(n), Trong đó, n = kích thước đầu vào a = Số lượng bài toán con trong đệ quy. n/b = kích thước của mỗi bài toán con. Tất cả các bài toán con được cho là có cùng kích thước. f(n) = chi phí công việc được thực hiện bên ngoài lệnh gọi đệ quy, bao gồm chi phí chia bài toán và chi phí hợp nhất các giải pháp
Chúng ta hãy lấy một ví dụ để tìm độ phức tạp thời gian của một bài toán đệ quy.
Đối với sắp xếp hợp nhất, phương trình có thể được viết như sau:
T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n) Trong đó, a = 2 (mỗi lần, một bài toán được chia thành 2 bài toán con) n/b = n/2 (kích thước của mỗi bài toán con bằng một nửa đầu vào) f(n) = thời gian cần thiết để chia bài toán và hợp nhất các bài toán con T(n/2) = O(n log n) (Để hiểu điều này, vui lòng tham khảo định lý tổng quát.)
Bây giờ, T(n) = 2T(n log n) + O(n) ≈ O(n log n)
1.7.3.Chia để trị so với phương pháp động
Phương pháp chia để trị chia một bài toán thành các bài toán con nhỏ hơn; các bài toán con này được giải quyết đệ quy thêm. Kết quả của mỗi bài toán con không được lưu trữ để tham khảo trong tương lai, trong khi đó, theo phương pháp động, kết quả của mỗi bài toán con được lưu trữ để tham khảo trong tương lai.
Sử dụng phương pháp chia để trị khi cùng một bài toán con không được giải quyết nhiều lần. Sử dụng phương pháp động khi kết quả của một bài toán con sẽ được sử dụng nhiều lần trong tương lai.
Hãy cùng tìm hiểu điều này qua một ví dụ. Giả sử chúng ta đang cố gắng tìm chuỗi Fibonacci. Khi đó,
Phương pháp chia để trị:
fib(n) If n < 2, return 1 Else , return f(n - 1) + f(n -2) Phương pháp động: mem = [] fib(n) If n in mem: return mem[n] else, If n < 2, f = 1 else , f = f(n - 1) + f(n -2) mem[n] = f return f
Trong phương pháp động, mem lưu trữ kết quả của từng bài toán con.
Ưu điểm của thuật toán chia để trị
Độ phức tạp của phép nhân hai ma trận sử dụng phương pháp ngây thơ là O(\(n^3\)),trong khi sử dụng phương pháp chia để trị (tức là phép nhân ma trận của Strassen) là O(\(n^{2.8074}\)).Phương pháp này cũng đơn giản hóa các bài toán khác, chẳng hạn như Tháp Hà Nội.
Phương pháp này phù hợp với các hệ thống đa xử lý.
