# GIẢI THÍCH THUẬT TOÁN TÌM FILM VÀ USER
## Sử dụng naive cho bài toán.
Input: $array$ với $m$ column và $n$ row, $threshold$
Cách này là mình đi hết tất cả các trường hợp submatrix, xong xem coi submatrix nào thỏa mãn điều kiện và lớn nhất thì mình sẽ giữ lại cái sub matrix
### 1: Tạo ra từng trượng hợp submatrix 1
từ $m$ column, bốc ra subset $m'$ với tất cả các trường hợp sẽ là $2^m$. Tương tự với $n$ row bốc ra subset $n'$ sẽ có tất cả $2^n$ cách. vậy để tạo ra được một submatrix hoàn chỉnh với size $m'*n'$, mình phải lấy từng subset của row đi với từng subset của column, thì tổng sẽ là $2^{m+n}$
### 2: Với mỗi submatrix, kiểm tra xem có thỏa mãn đề bài
**Nếu như chỉ cần 1 điều kiện nào không thỏa bài toán thì mình bỏ subarray đó luôn và kiểm tra subarray tiếp theo như bước 1**

* Điều kiện 1: check xem có N/A (denote là -1) trong subarray bằng cách chạy hết phần tử của subarray. cái này thì sẽ tốn $n'*m'$ time.
* Điều kiện 2:
* sau khi không có N/A. tiếp tục tính correlation của từng cặp user 1, sẽ có $C^{2}_{n'}$ cặp khác nhau cần tính. Với mỗi lần tính, mình cũng phải đi hết $m'$ film. Vì vậy tổng time complexity là $n'^2*m'=n^2*m$ trong worst case.(công thức tính correlation vs tính combination nó vậy nên hong hiểu thì google thoi :)))).
* khi mình tính correlation mà chỉ cần 1 thằng bé hơn threshold thui thì cho cái subarray đó chim cút luôn, đi mà tính subarray khác.
### 3: Lưu lại cái subarray lớn nhất:
sau khi xong 1 subarray mà không có bị loại bất cứ thứ gì ở bước 2, thì mình sẽ lưu lại cái submatrix này. rồi tiếp tục đi tìm submatrix khác, nếu thằng mới mà cũng thỏa đủ điều kiện mà to hơn cái đầu (so sánh $m'*n'$) thì mình update cái mới.

vậy là xong hết rùi, chỉ cần show ra cái subarray mình lưu lại thui. tổng thiệt hại về time là $2^{m+n}*(nm+n^2m)=2^{m+n}*n^2m$. Còn về space chỉ là $n+m$ để lưu cái subarray của row và column của mình
## Upgraded algorithm
Input: $array$ với $m$ column và $n$ row, $threshold$

So với cái Naive, cái này thay đổi hướng tiếp cận đề bài và nó sẽ ảnh hướng đến bước 1 và bước 2 của Naive.

### 1: Bốc phim ra
thay vì mình generate ra toàn bộ subset của row và column, thì mình chỉ cần generate ra subset của column, còn row mình sẽ thay đổi hướng tương tác.
### 2: kiếm những users mà correlation của nó với nhau phải lớn hơn threshold(vector input corrlation sẽ có size là $m'$)
* đầu tiên mình phải lọc N/A. Nhưng khác với Naive, nếu mình gặp N/A mình sẽ không bỏ luôn cái subset của column rùi qua subset khác. Thay vào đó mình chỉ bỏ đi cái user mà có N/A. Nói dễ hiểu hơn là mình chỉ giữ lại $n'$ users mà xem đủ $m'$ films đang xét. bước này thì tốn $n*m'$ và $n*m$ in worst case time complexity
* sau khi lọc xong user coi phim ra, mình sẽ có $n'$ coi đủ $m'$ phim. Từ đó mình có thể bốc từng cặp user ra tính correlation lại với nhau(tốn time $n'^2*m'$ thì sẽ có worst case $n^2*m$). Và mình sẽ vẽ được một correlation matrix. Cái correlation matrix này cũng chính là 1 adjacency matrix, mình sẽ denote những correlation nào lớn hơn threshold là 1, và 0 cho những cái còn lại. Và lúc này, adjancency matrix của mình nó equivalent với 1 cái graph với 1 là có edge giữa 2 node còn 0 là ko có node.
* Bài toán của mình là tìm tất cả các users mà đều có correlation lớn hơn threshold, tức là tìm complete subgraph lớn nhất trong cái graph mình mới hình thành. Để xử lý bài toán này, mình sẽ xài **greedy algorithm** với time complexity là n^3 và space là n^2, nó sẽ nhanh hơn nhưng không cho ra kết quả chính xác hơn thuật toán đúng để tìm complete subgraph(cái thuật toán đúng là $3^{n/3}$ lận). Cách tìm thì hơi dài dòng nên xin ghé link này để biết thêm https://iq.opengenus.org/greedy-approach-to-find-single-maximal-clique/
### 3: Bước 3 này giống y chang bước 3 naive
những user và mình tìm được hợp với subset film ban đầu tạo ra submatrix $m'*n'$. sau đó mình đi tìm tiếp những subset của column rồi update cái nào lớn nhất thui

tổng thiệt hại time sẽ là $2^m*(n^2*m+n^3)$ còn space là $m*n^2$ với $n^2$ là để lưu graph