Học Algorithms, Ngày 02

Hôm nay học "Week 1" [quick-find] & [quick-union]. Đã thấy khó hơn nhưng vẫn hiểu được không nhiều thì ít hơ hơ.

Ghi lại vài chú ý chính.

1. [quick-find]

Data structure.
・Integer array id[] of length N.
・Interpretation: p and q are connected if and only if they have the same id.

Operations.
・Find : check if p and q have the same id.
・Union : to merge components containing p and q, change all entries whose id equals id[p] to id[q].

quick-find is too slow. 

union is too expensive. It takes N*N array accesses to process a sequence of N union commands on N objects.

2. [quick-union]

Data structure. 

・Integer array id[] of length N. 

・Interpretation: id[i] is parent of i. 

・Root of i is id[id[id[...id[i]...]]].

Operations.

・Find : check if p and q have the same root. 

・Union : to merge components containing p and q, set the id of p's root to the id of q's root.

quick-union is also too slow.

find too expensive (could be N array accesses).

Túm lại là 2 thuật toán quick-find và quick-union có thể giải quyết được vấn đề [dynamic connectivity], một cái thì "tìm nhanh" , cái còn lại thì "hợp nhanh". Tuy nhiên 2 thuật toán này không hiệu quả về mặt hiệu năng, quá chậm khi số phần tử N lớn. Hai cái này gọi là "quandratic algorithms" nghĩa là thời gian tính toán tăng theo cấp số bình phương của kích cỡ.

Hôm sau sẽ học Week 1 [quick-union improvements] & [union-find applications].