Trong Tin học, thuật toán tìm kiếm trên một cây cân bằng (một dạng graph đặc biệt) đòi hỏi số bước di chuyển là $P(n)$ ứng với số cây có bậc $n$ và xác định theo công thức sau
$P_n(i)=\frac{(i-1)(P_{i-1}+1)+(n-i)(P_{n-i}+1)}{n}$ và $P_n=\frac{1}{n}\sum\limits_{i=1}^nP_n(i)$
Hãy đánh giá độ phức tạp thuật toán này.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh
