ĐỘ PHỨC TẠP THỜI GIAN CỦA BFS ĐỐI VỚI CÂY ĐỒ THỊ

 

ĐỘ PHỨC TẠP THỜI GIAN CỦA BFS ĐỐI VỚI CÂY ĐỒ THỊ

Ở đây chúng ta không nói đến cách thuật toán hoạt động ra sao, chỉ xét đến độ phức tạp của thuật toán.

(Các bạn nên xem các bài trước về cách tính big O trước khi xem bài này nhé)

Ta sẽ tóm lại các bước của quá trình duyệt BFS rồi tiến hành phân tích:

B1: Khởi tạo một danh sách là một queue

B2: Truyền vào danh sách node bắt đầu

B3: Lặp

B3.1: Nếu danh sách hết thì sẽ kết thúc (false)

B3.2: Lấy một phần tử ra khỏi danh sách, đặt là current

B3.3: Nếu current là goal thì kết thúc (true)

B3.4: Duyệt từng con của nó và thêm vào danh sách

Tiếp theo ta tiến hành đặt ký hiệu: Gọi b là độ sâu tối đa của cây và d là số nhánh tối đa của nó như hình.

Vì sao ta lại chọn là tối đa? Vì một cây thông thường thì số nhánh cũng như độ sâu từng node lá sẽ không cố định, nên ta sẽ xét trường hợp xấu nhất để thuận tiện tính toán cũng như là biết được giới hạn của nó.

Trong thuật toán ta để ý rằng vòng lặp ở bước ba số lần lặp của nó chính là số lần duyệt đỉnh current. Và mỗi lần lấy current sẽ duyệt b lần để lấy đỉnh con (B3.4). Các bước khác chỉ là cố định O(1) nên ta không xét.

Giả sử như không tồn tại bước duyệt B3.4, độ phức tạp của thuật toán sẽ chính là số lần duyệt qua tất cả các node của đồ thị. Như thế ta sẽ tính thử số lần duyệt node của đồ thị.

Ta thấy đồ thị có nguyên tắc sau (hình trên): Với b = 3, tại vị trí depth = 0 thì số node sẽ là b⁰ = 1, depth = 1 thì số node là b¹ = 3,... Như vậy tại vị trí k bất kỳ thì số node sẽ là b^k. Đặt k = d => vị trí tối đa sẽ duyệt b^d node. Tổng số node ta có thể duyệt qua sẽ là:

f’(b,d) = b⁰ + b¹ + b² + ... + b^d

Nhưng ta nhớ rằng với mỗi node gọi là current ta lấy ra và duyệt, sẽ tồn tại bước B3.4 là duyệt qua b node con để thêm vào danh sách. Như vậy hàm số thực sự sẽ là:

 f(b,d) = (b⁰ + b¹ + b² + ... + b^{d - 1})*b + b^d

Vì sao tại số lần duyệt b^d không được nhân với b? Tại đây là lần duyệt của các nút lá. Ở nút lá không tồn tại nút con để duyệt cho nên không được tính vào.

f(b,d) = b¹ + b² + b³ + ... + b^d + b^d

f(b,d) = b¹ + b² + b³ + ... + 2b^d

Ta nhớ rằng khi xét big O ta chọn hệ số có sự biến đổi lớn nhất. Ở đây là 2b^d.

Tiếp theo ta loại bỏ hệ số không cần thiết là 2, vì nó không làm thay đổi bản chất của một đồ thị hàm mũ. (độ biến thiên vẫn không thay đổi)

Như vậy ta có thể kết luận độ phức tạp của thuật toán là O(b^d)  

Lời kết: Đây hoàn toàn là bài phân tích của riêng mình thông qua kiến thức mình có được, nếu có sai sót mong các bạn đóng góp thêm!

Nội dung bài viết thuộc về Lê Công Diễn.

 

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn