Ứng dụng cây nhị phân tìm kiếm trong bài toán biểu diễn phân số a/b dưới dạng số thập phân vô hạn tuần hoàn

Độ phức tạp để xây cây nhị phân tìm kiếm là:
log1 + log2 + … + logk = O(k*logk)

Độ phức tạp để tìm kiếm một phần tử: log1 + log2 + … + logk = O(k*logk)

Nếu sử dụng thuật toán bình thường để tìm kiếm thì độ phức tạp là:
1 + 2 + … + k = k(k+1)/2 = O(k^2)

Bạn có thể sửa lại code sau để xây dựng thuật toán mới bằng cách sử dụng Cây nhị phân tìm kiếm: https://tosonnguyen.wordpress.com/2014/05/25/bieu-dien-phan-so-ab-duoi-dang-so-thap-phan-vo-han-tuan-hoan/
(sửa code ở đoạn này for(it = L.begin(); it != L.end(); it++){)

Chú ý riêng: Trong toán học thì:
log1 + log2 + … + logk = logk!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: