Ở đây chúng ta sẽ xem cách sử dụng phương pháp thay thế để giải quyết các quan hệ lặp lại. Chúng tôi sẽ lấy hai ví dụ để hiểu nó theo cách tốt hơn.
Giả sử chúng ta đang sử dụng kỹ thuật tìm kiếm nhị phân. Trong kỹ thuật này, chúng tôi kiểm tra xem phần tử có ở cuối hay không. Nếu điều đó xuất hiện ở giữa, thì thuật toán kết thúc, nếu không, chúng tôi lấy đi lặp lại một trong hai mảng con bên trái và bên phải từ mảng thực tế. Vì vậy trong mỗi bước kích thước của mảng giảm đi n / 2. Giả sử thuật toán tìm kiếm nhị phân mất T (n) lượng thời gian để thực thi. Điều kiện cơ sở mất O (1) lượng thời gian. Vì vậy, phương trình lặp lại sẽ giống như dưới đây -
$$ T (n) =\ begin {case} T (1) &for \:n \ leq 1 \\ 2T (\ frac {n} {2}) + c &for \:n> 1 \ end {case } $$
Giải quyết - Chúng tôi sẽ thay thế công thức trong mỗi bước để nhận được kết quả -
$$ T (n) =T (\ frac {n} {2}) + c $$
Bằng cách thay thế T (N / 2), chúng ta có thể viết,
$$ T (n) =(T (\ frac {n} {4}) + c) + c $$
$$ T (n) =T (\ frac {n} {4}) + 2c $$
$$ T (n) =T (\ frac {n} {8}) + 3c $$
$$ T (n) =T (\ frac {n} {2 ^ {k}}) + kc $$
Bây giờ, nếu $$ (\ frac {n} {2 ^ {k}}) $$ đạt đến 1, nó chỉ ra rằng 2 k là n. Vì vậy, giá trị của k là log 2 𝑛
Độ phức tạp của T (n) =ϴ (log n)
Tương tự, nếu chúng ta chọn một ví dụ khác như sắp xếp hợp nhất, thì trong trường hợp đó, chúng ta chia danh sách thành hai phần. Sự phân chia này diễn ra cho đến khi kích thước danh sách chỉ còn 1. Sau đó, chúng tôi hợp nhất chúng theo thứ tự đã sắp xếp. Thuật toán hợp nhất mất O (n) lượng thời gian. Vì vậy, nếu thuật toán sắp xếp hợp nhất đang chiếm T (n) lượng thời gian, thì bằng cách chia nó thành hai nửa và thực hiện cùng một nhiệm vụ cho mỗi người trong số họ, chúng sẽ mất T (n / 2), v.v. Vì vậy, mối quan hệ lặp lại sẽ như dưới đây -
$$ T (n) =\ begin {case} T (1) &for \:n =1 \\ 2T (\ frac {n} {2}) + cn &for \:n> 1 \ end {case} $$
Giải quyết - Chúng tôi sẽ thay thế công thức trong mỗi bước để nhận được kết quả -
$$ T (n) =2T (\ frac {n} {2}) + cn $$
Bằng cách thay thế T (N / 2), chúng ta có thể viết,
$$ T (n) =2 (2T (\ frac {n} {4}) + \ frac {cn} {2}) + cn $$
$$ T (n) =4T (\ frac {n} {4}) + 2cn $$
$$ T (n) =8T (\ frac {n} {8}) + 3cn $$
$$ T (n) =2 ^ {k} T (\ frac {n} {2 ^ {k}}) + kcn $$
Bây giờ, nếu $$ (\ frac {n} {2 ^ {k}}) $$ đạt đến 1, nó chỉ ra rằng 2 k là n. Vì vậy, giá trị của k là log 2 𝑛. Và T (n) sẽ -
𝑇 (𝑛) =𝑛𝑇 (1) + 𝑐𝑛 log 2 𝑛
Độ phức tạp là θ (n log n)