Thuật toán tìm GTLN và GT lớn thứ 2 trong mảng với số phép so sánh xấp xỉ 1.5n và n + logn - 2

minhcanhtu · October 13, 2018, 11:14pm

Hi mọi người. Tình hình là mình đang làm một vài exercise break trong week 1 của 1 khóa algorithm trên Coursera. Tóm tắt đề bài thì yêu cầu là cho trước 1 array và tìm GTLN và GT lớn thứ 2 trong array đó với đpt là 1.5n và n + logn - 2.
Mình có tìm thấy 1 answer rất hay trên stackexchange sau: https://cs.stackexchange.com/questions/83022/find-largest-and-second-largest-elements-of-the-array/83056#83056
Nhìn sơ qua thì để làm được với đpt 1.5n, đầu tiên mình sẽ duyệt mảng O(n) để tách từng pair. Sau đó mình sẽ lọc được 3 giá trị là GTLN của các pairs, GT lớn thứ 2 của các pairs và GT nằm cùng pair với GTLN vừa tìm được. Với lần duyệt này, ta chỉ chạy n/2 lần nên có thể thấy đpt xấp xỉ n + n/2 = 1.5n.
Nhưng mình vẫn còn 1 chút khúc mắc ở chỗ này. Mình chưa hình dung được cách tìm 3 giá trị là GTLN của các pairs, GT lớn thứ 2 của các pairs và GT thứ 3. Nếu như vẫn dùng cách duyệt thì trong lần duyệt O(n / 2) ta sẽ tìm được GTLN của các pairs, như còn để tìm GT lớn thứ 2 của các pairs chẳng lẽ phải duyệt lại lần nữa ? (như thế lại thành 2n mất)
Nhờ mọi người giúp đỡ mình chỗ này ạ!
Thank you so much.

Phong_Ky_Vo · October 14, 2018, 2:44am

Hi Secret
Theo mình hiểu thì điểm mấu chốt của thuật toán :

người ta chia mảng thành 2 phần và sau đó tìm giá trị lớn nhất trên các phần A1 và A2.
Giả sử A1 > A2 (Trường hợp A1 = A2 thì không giảm được xuống 1.5n). Khi đó giá trị lớn thứ hai B thỏa mãn điều kiện A1 > B >= A2.
2.1 Nếu B > A2 thì B thuộc phần mảng thứ nhất (Chứa A1) vậy duyệt tìm trên đó 0.5n vì nếu B thưộc phâng thứ hai chứa A2 thì A2 không phải là giá trị lớn nhất của phần hai vì có B > A2.
2.2 Nếu B=A2 thì phần tử lớn thứ hai trong phần mảng thứ nhất B’ <= A2.

P/S Nếu chia mảng thành vô hạn các phần thì khi đó tính giới hạn sẽ được 1.5n (Mỗi phần có 2 phần tử). Lần đầu tìm giá trị lớn nhất trên cặp 2 phần tử (tìm A1 và A2) 0.5n sau đó tìm giá trị lớn nhất trong số các A1, A2, … An 0.5n giả sử là Ax khi đó phần tử còn lại của nhóm Ax chính là B. Thay Ax bằng B rồi tìm phần tử lớn nhất 0.5n.

tntxtnt · September 9, 2019, 12:13am

mỗi lần duyệt mảng n phần tử tốn có n/2 so sánh, mảng ban đầu có n = 2^k phần tử thì sẽ mất 2^k-1 + 2^k-2 + … + 2 + 1 = 2^k - 1 = n - 1 so sánh để tìm ra phần tử lớn nhất.

để tìm phần tử lớn thứ 2 thì phải biết được phần tử lớn nhất thắng những phần tử nào. Vì vậy phải có 1 bản ghi ai thắng ai thua trong từng cặp đấu

 1   4   5   2   7   9  [10] 19
  \ /     \ /     \ /     \ /   
   4       5      [9]      19
     \   /           \   /
      [5]              19
          \         /
              19

 1   4   5   2   7   9  10  19   từng đôi một kề nhau vs nhau
[4]  1  [5]  2  |9|  7 |19| 10   4 vs 5, 9 vs 19
{5}  1   4   2 {19}  7   9  10   5 vs 19
19   1   4   2   5   7   9  10   -- 19 đánh bại 5, 9, 10, lần lượt là a[4], a[6], a[7]
                                    ở mảng sau cùng đã bị hoán đổi vị trí

bản ghi là

1   0   1   1
 \ /     \ /
  1       1
    \   /
      1

1 tức là lhs vs rhs thì rhs thắng, 0 là lhs thắng

từ bản ghi này có thể truy ra những “bại tướng” của nhà vô địch, lúc này nằm ở vị trí a[0]

                           - bại tướng đầu tiên luôn luôn là a[n/2], vì phần tử lớn
               +n/2          nhất nằm ở vị trí 0, và bại tướng của vòng này phải +n/2
      1                    - 1 cho biết trước cặp đấu cuối cùng 19 nằm ở vị trí vị trí cách vị trí cũ n/2,
    /   \      +n/4          như vậy mà vòng này bại tướng là a[(0 + n/2) + n/4]
  1       1                - 1 cho biết trước cặp đấu cuối cùng 19 nằm ở vị trí cách vị trí cũ n/4,
 / \     / \   +n/8          như vậy mà vòng này bại tướng là a[(n/2 + n/4) + n/8]
1   0   1   1              - ko cần thiết

từ bản ghi là mảng bool có kích cỡ n/2 - 1, có thể truy ra log₂n bại tướng của nhà vô địch là a[0+4], a[4+2], a[6+1], rồi so sánh tìm phần tử lớn nhất trong log₂n bại tướng, tốn log₂n - 1 so sánh nữa.

tổng cộng tốn n - 1 + log₂n - 1 = n + log₂n - 2 so sánh và 1 đống bộ nhớ :V

vd khác :V

 1   4   5   2   9  19  10   7   từng đôi 1 kề nhau vs nhau
[4]  1  [5]  2 |19|  9 |10|  7   4 vs 5, 19 vs 10
{5}  1   4   2 {19}  9  10   7   5 vs 19
19   1   4   2   5   9  10   7   -- 19 đánh bại 5, 10, 9, lần lượt là a[4], a[5], a[6]
                                    ở mảng sau cùng đã bị hoán đổi vị trí
 
 1   4   5   2  [9] 19  10   7
  \ /     \ /     \ /     \ /   
   4       5       19     [10]
     \   /           \   /
      [5]              19
          \         /
              19
              
1   0   1   0
 \ /     \ /
  1       0
    \   /
      1
      
                           - bại tướng đầu tiên luôn luôn là a[n/2], vì phần tử lớn
               +n/2          nhất nằm ở vị trí 0, và bại tướng của vòng này phải +n/2
      1                    - 1 cho biết trước cặp đấu cuối cùng 19 nằm ở vị trí cách vị trí cũ n/2,
    /   \      +n/4          như vậy mà vòng này bại tướng là a[(0 + n/2) + n/4]
  1       0                - 0 cho biết trước cặp đấu cuối cùng 19 nằm ở vị trí cách vị trí cũ 0,
 / \     / \   +n/8          như vậy mà vòng này bại tướng là a[(n/2 + 0) + n/8]
-   -   -   -              - ko cần thiết
      
a[0+4], a[4+2], a[4+1] trong mảng a
19   1   4   2   5   9  10   7
là 5, 10, 9 lần lượt là các bại tướng của 19 theo thứ tự chung kết bán kết tứ kết :V

tntxtnt · October 14, 2018, 4:28am

nó vẽ ra cho ghê vậy thôi chứ làm 1 cái mảng ghi bại tướng cũng xong ấy mà

 1   4   5   2   7   9  10  19

thành mảng bại tướng

a[0]: (ko qua nổi vòng 1 :V)
a[1]: 0
a[2]: 3, 1
a[3]: 
a[4]: 
a[5]: 4
a[6]: 
a[7]: 6, 5, 2

vô địch là a[7], a[6], a[5], a[2] lần lượt thua nhà vô địch, huy chương bạc là 1 trong 3 chú này (ko phải là chú a[2] có 5 điểm ăn hôi như ông nội Croatia). Phải cho 3 chú này đấu với nhau tiếp 3-1 = 2 trận nữa mới tìm ra ai về nhì :V