Tìm kiếm và Sắp xếp Đệ Quy
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | Chia để trị |
| merge sort/mɜːdʒ sɔːt/ | Sắp xếp gộp |
| merge/mɜːdʒ/ | Gộp |
Đệ quy gặp tìm kiếm và sắp xếp
- Ý tưởng chia để trị tương tự cũng làm nền tảng cho tìm kiếm nhị phân đệ quy và sắp xếp gộp đệ quy.
- Chia đôi vấn đề, giải quyết các nửa, rồi kết hợp.
- Tìm kiếm nhị phân đệ quy tìm kiếm một nửa bằng cách gọi chính nó lên nửa đó.
- Sắp xếp gộp sắp xếp mỗi nửa, sau đó gộp các nửa đã sắp xếp lại với nhau.
Tìm kiếm nhị phân đệ quy
- Trường hợp cơ sở: một vùng rỗng có nghĩa là mục tiêu không được tìm thấy.
- Nhìn vào phần giữa. Nếu nó là mục tiêu, trả về chỉ mục của nó.
- Nếu mục tiêu nhỏ hơn, đệ quy trên nửa trái; nếu lớn hơn, nửa phải.
- Mỗi lần gọi chia đôi vùng tìm kiếm — cùng một độ phức tạp
O(log n), nhưng viết dưới dạng đệ quy.
Sắp xếp gộp
- Chia mảng thành hai nửa; sắp xếp từng nửa đệ quy.
- Trường hợp cơ sở: một mảng có 0 hoặc 1 phần tử đã được sắp xếp sẵn.
- Gộp: duyệt qua cả hai nửa đã sắp xếp, luôn lấy phần tử nhỏ nhất ở đầu tiên.
- Nhanh hơn nhiều so với các thuật toán
n²— tốn khoảngn log ncông việc.
Tại sao chia để trị chiến thắng
- Việc chia đôi vấn đề ở mỗi bước mang lại hệ số
log n. - Sắp xếp gộp với độ phức tạp
n log nvượt trội hơn sắp xếp theo lựa chọn/sắp xếp theo chèn có độ phức tạpn²trên các mảng lớn. - Trường hợp cơ sở (vùng rỗng hoặc một phần tử) dừng mọi nhánh.
- Cùng hình dáng với mọi đệ quy: chia xuống dưới, kết hợp trở lên trên.
Tìm kiếm nhị phân đệ quy đệ quy trên MỘT nửa (mục tiêu chỉ nằm ở một bên); sắp xếp gộp đệ quy trên CẢ HAI nửa và sau đó gộp chúng lại. Cả hai đều cần trường hợp cơ sở — vùng rỗng có nghĩa là "không tìm thấy" đối với tìm kiếm; mảng 0 hoặc 1 phần tử đã được sắp xếp sẵn đối với sắp xếp gộp. Chia để trị chính là yếu tố khiến chúng nhanh (O(log n) và O(n log n)).
Sắp xếp gộp trên [3, 1, 2, 4]:
- Chia thành
[3, 1]và[2, 4]; sắp xếp từng phần →[1, 3]và[2, 4]. - Gộp: lấy 1, sau đó 2, sau đó 3, sau đó 4 →
[1, 2, 3, 4]. - Mỗi lần gộp sẽ lần lượt chọn phần tử đầu nhỏ hơn.
Tìm kiếm nhị phân đệ quy đệ quy trên một nửa (trạng thái cơ sở: khoảng rỗng = không tìm thấy) cho O(log n) tìm kiếm. Sắp xếp hợp nhất đệ quy trên cả hai nửa và gộp chúng (trạng thái cơ sở: 0 hoặc 1 phần tử) cho O(n log n) sắp xếp. Cả hai đều là chia để trị: chia xuống dưới, kết hợp lên trên — nhanh hơn nhiều so với n².
Merge sort chia đôi, sau đó hợp nhất lên trên
Các phần tử đơn lẻ đã được sắp xếp (base case); hợp nhất kết hợp chúng lên trên.
Tìm kiếm nhị phân đệ quy trên...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Mục tiêu chỉ nằm ở một bên của phần tử giữa.
Merge sort đệ quy trên...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Sắp xếp mỗi nửa, sau đó hợp nhất hai nửa đã sắp xếp.
Base case cho merge sort là mảng có...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Một (hoặc không) phần tử không cần sắp xếp.
Thời gian chạy của merge sort khoảng...
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
log n cấp độ chia đôi, n công việc mỗi cấp độ.
Cả tìm kiếm nhị phân đệ quy và merge sort đều là thuật toán chia để trị.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Cả hai chia bài toán thành hai phần và đệ quy.
Sắp xếp thứ tự bước hợp nhất cho hai nửa [1,3] và [2,4].
Độ khó 3/5 · 200 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Luôn lấy phần tử nhỏ hơn ở đầu: 1, 2, 3, 4.