Quá trình sắp xếp nhanh là một thuật toán sắp xếp được phát triển bởi Tony Hall. Trong trường hợp trung bình, sắp xếp n mục cần O (nlogn) lần so sánh. Trong trường hợp tồi tệ nhất, cần O (n2) lần so sánh, nhưng điều này không phổ biến. Trong thực tế, sắp xếp nhanh thường nhanh hơn nhiều so với các thuật toán khác của O (nlogn) vì vòng lặp bên trong của nó có thể được thực hiện hiệu quả trên hầu hết các kiến trúc.
Phân loại nhanh sử dụng chiến lược chia và chinh phục để chia một danh sách thành hai danh sách con.
Các bước của thuật toán:
Một, chọn một phần tử từ hàng số, gọi là pivot, và sau đó chọn một phần tử khác.
2, sắp xếp lại hàng số, tất cả các yếu tố nhỏ hơn giá trị tham khảo được đặt trước và tất cả các yếu tố lớn hơn giá trị tham khảo được đặt sau (tương tự số có thể đến bất kỳ bên nào); sau khi thoát khỏi phân vùng này, tiêu chuẩn nằm ở vị trí trung gian của hàng số. Điều này được gọi là hoạt động phân vùng.
3, recursively (recursive) sắp xếp các chuỗi số con nhỏ hơn các phần tử giá trị cơ bản và các chuỗi số con lớn hơn các phần tử giá trị cơ bản.
Trường hợp cơ bản nhất của sự hồi quy là số lượng hàng có kích thước bằng 0 hoặc 1, nghĩa là nó luôn được sắp xếp tốt. Mặc dù tiếp tục hồi quy, nhưng thuật toán này luôn thoát ra vì trong mỗi lần lặp lại, nó sẽ đưa ít nhất một phần tử đến vị trí cuối cùng của nó.
Heapsort là một thuật toán sắp xếp được thiết kế để sử dụng cấu trúc dữ liệu của cột. Cột là một cấu trúc gần như hoàn toàn hai phân tử, đồng thời đáp ứng các tính chất của cột: giá trị khóa hoặc chỉ mục của các nút con luôn nhỏ hơn hoặc lớn hơn các nút cha của nó.
Sự phức tạp thời gian trung bình của sắp xếp chồng là O (nlogn).
Các bước của thuật toán:
1, tạo một hàng H [0...n-1]
2, thay thế đầu (max) và cuối
3, giảm kích thước hàng xuống 1 và gọi shift_down ((0), nhằm điều chỉnh dữ liệu ở đầu mảng mới đến vị trí thích hợp
4 và lặp lại bước 2 cho đến khi kích thước của hàng là 1
Mergesort là một thuật toán sắp xếp hiệu quả được xây dựng dựa trên các hoạt động sắp xếp; thuật toán này là một ứng dụng rất điển hình của phương pháp phân chia và chinh phục.
Các bước của thuật toán:
1, Ứng dụng không gian để có kích thước là tổng của hai chuỗi đã được sắp xếp, không gian này được sử dụng để lưu trữ các chuỗi đã được hợp nhất
2, đặt hai con trỏ, vị trí bắt đầu của hai chuỗi đã được sắp xếp
3, so sánh các phần tử được chỉ ra bởi hai con trỏ, chọn phần tử tương đối nhỏ vào không gian hợp nhất và di chuyển con trỏ đến vị trí tiếp theo
Bước 4: Lặp lại bước 3 cho đến khi một trong các chỉ số đạt đến cuối chuỗi
5, sao chép tất cả các phần tử còn lại của chuỗi khác trực tiếp vào cuối chuỗi kết hợp
Một thuật toán tìm kiếm hai điểm là một thuật toán tìm kiếm một phần tử cụ thể trong một mảng có thứ tự. Quá trình tìm kiếm bắt đầu từ phần tử trung gian của mảng, và kết thúc nếu phần tử trung gian chính là phần tử cần tìm kiếm; nếu một phần tử cụ thể lớn hơn hoặc nhỏ hơn phần tử trung gian, tìm kiếm trong một nửa của mảng lớn hơn hoặc nhỏ hơn phần tử trung gian, và bắt đầu so sánh từ phần tử trung gian như ban đầu. Nếu ở một bước nào đó, số liệu không có nghĩa là không thể tìm thấy.
BFPRT giải quyết các vấn đề cổ điển, đó là chọn các phần tử lớn nhất (k nhỏ nhất) trong một chuỗi n phần tử, thông qua phân tích khéo léo, BFPRT có thể đảm bảo rằng nó vẫn còn phức tạp thời gian tuyến tính trong trường hợp tồi tệ nhất. Ý tưởng của thuật toán này tương tự như ý tưởng sắp xếp nhanh, tất nhiên, để cho phép thuật toán vẫn đạt được độ phức tạp thời gian o (n) trong trường hợp tồi tệ nhất, năm tác giả của thuật toán đã xử lý tinh tế.
Các bước của thuật toán:
1, chia n phần tử thành n/5 (bề trên) nhóm.
2, lấy số trung của mỗi nhóm, bất kỳ cách sắp xếp nào, ví dụ như chèn sắp xếp.
3, một thuật toán chọn gọi hồi quy tìm ra trung bình của tất cả các số trung bình trong bước trước, được đặt là x, và trong trường hợp có một số trung bình lẻ, được đặt là chọn một trong số trung gian nhỏ hơn.
4, để chia một mảng bằng cách sử dụng x, hãy đặt số ít hơn x bằng k và số lớn hơn x là n - k.
5, nếu i==k, trả về x; nếu i
Điều kiện chấm dứt: khi n = 1, trở lại là phần tử nhỏ i.
Depth-First-Search là một thuật toán tìm kiếm; nó đi sâu dọc theo cây, trải qua các nút trên cây, và phân nhánh cây tìm kiếm càng sâu càng tốt. Khi tất cả các bên của nút v đã được tìm kiếm, tìm kiếm sẽ quay trở lại các nút bắt đầu bên cạnh nút v được tìm thấy. Quá trình này tiếp tục cho đến khi tất cả các nút đã được tìm thấy có thể truy cập từ nút nguồn. Nếu không có nút được tìm thấy, chọn một trong số đó làm nút nguồn và lặp lại quá trình này, toàn bộ quá trình lặp lại cho đến khi tất cả các nút được truy cập.
Tìm kiếm ưu tiên sâu là một thuật toán cổ điển trong đồ họa, sử dụng thuật toán tìm kiếm ưu tiên sâu để tạo ra bảng xếp hạng vị trí tương ứng của đồ họa đích, sử dụng bảng xếp hạng vị trí để giải quyết một số vấn đề đồ họa liên quan như vấn đề đường dẫn tối đa, v.v.
Một số người cho rằng, "Điều này là một sự thay đổi lớn trong lịch sử".
Một, truy cập vào đỉnh v;
2, bắt đầu từ điểm kết nối lân cận chưa được truy cập của v, truy cập vào đồ họa theo cách ưu tiên sâu; cho đến khi các đỉnh trong đồ họa và đường dẫn của v được truy cập;
3, nếu vẫn còn các đỉnh chưa được truy cập trong biểu đồ, hãy bắt đầu từ một đỉnh chưa được truy cập, và thực hiện lại việc đi sâu ưu tiên cho đến khi tất cả các đỉnh trong biểu đồ đã được truy cập.
Những mô tả trên có thể khá trừu tượng, ví dụ như:
DFS khởi hành từ v, truy cập vào bất kỳ đỉnh nào của nó, bắt đầu với đỉnh v trong một trong các biểu đồ truy cập; sau đó khởi hành từ w1, truy cập vào đỉnh w2 mà đã không được truy cập; sau đó khởi hành từ w2, truy cập tương tự,... và tiếp tục như vậy cho đến khi đến đỉnh u mà tất cả các đỉnh lân cận đã được truy cập.
Sau đó, quay lại một bước, quay lại đỉnh mà bạn vừa truy cập lần trước để xem liệu có các đỉnh lân cận khác chưa được truy cập. Nếu có, truy cập vào đỉnh này, sau đó bắt đầu từ đỉnh này và thực hiện truy cập tương tự như trước; nếu không, quay lại một bước nữa và tìm kiếm.
Breadth-First-Search là một thuật toán tìm kiếm đồ họa. Nói một cách đơn giản, BFS là bắt đầu từ các nút gốc và đi dọc theo chiều rộng của cây. Nếu tất cả các nút được truy cập, thuật toán sẽ ngừng.
Các bước của thuật toán:
1, đầu tiên đặt các nút gốc vào hàng.
2, lấy nút đầu tiên trong hàng và kiểm tra xem nó có phải là mục tiêu không.
Nếu tìm thấy mục tiêu, kết thúc tìm kiếm và gửi lại kết quả. Nếu không, hãy thêm tất cả các subnode trực tiếp chưa được kiểm tra vào hàng đợi.
Nếu hàng là trống, toàn bộ đồ thị đã được kiểm tra và không có mục tiêu nào trong đồ thị. Kết thúc tìm kiếm và trả về thông báo không tìm thấy mục tiêu.
Bước 4: Lặp lại bước 2:
Các thuật toán Dijkstra được đề xuất bởi nhà khoa học máy tính người Hà Lan Ezher Dijkstra. Các thuật toán Dijkstra sử dụng tìm kiếm ưu tiên rộng để giải quyết vấn đề đường ngắn nhất của một nguồn đơn của một đồ thị hướng không có quyền tiêu cực, và cuối cùng các thuật toán nhận được một cây đường ngắn nhất.
Các đầu vào của thuật toán bao gồm một đồ thị có trọng lượng G, và một đỉnh nguồn S trong G. Chúng ta dùng V để biểu thị tập hợp tất cả các đỉnh trong G. Mỗi cạnh trong đồ thị là một cặp các phần tử có trật tự được tạo ra bởi hai đỉnh. U, v cho thấy có một đường dẫn từ đỉnh u đến v. Chúng ta dùng E để biểu thị tập hợp tất cả các cạnh trong G, trong khi trọng lượng của cạnh được xác định bởi hàm trọng lượng w: E→[0,∞].
Do đó, w (u, v) là trọng lượng không âm từ đỉnh u đến đỉnh v. trọng lượng bên có thể tưởng tượng là khoảng cách giữa hai đỉnh. trọng lượng của đường dẫn giữa hai điểm là tổng trọng lượng của tất cả các bên trên đường dẫn đó. Có đỉnh s và t được biết đến ở V, thuật toán Dijkstra có thể tìm ra đường trọng lượng tối thiểu từ s đến t (ví dụ, đường ngắn nhất).
Các bước của thuật toán:
1, giá trị khoảng cách tương ứng giữa các đỉnh trong T, với thời gian ban đầu là S = {V0}, T = {rằng các đỉnh còn lại}
Nếu có
2, chọn từ T một đỉnh W có giá trị khoảng cách nhỏ nhất và không nằm trong S, và thêm vào S
3, sửa đổi giá trị khoảng cách giữa các đỉnh trong T còn lại: nếu thêm W vào đỉnh giữa, giảm giá trị khoảng cách từ V0 đến Vi, bạn sẽ sửa đổi giá trị khoảng cách này
Lặp lại các bước 2 và 3 ở trên cho đến khi tất cả các đỉnh trong S được bao gồm, tức là W = Vi
Dynamic programming là một phương pháp được sử dụng trong toán học, khoa học máy tính và kinh tế để giải quyết các vấn đề phức tạp bằng cách phân giải các vấn đề gốc thành các vấn đề con tương đối đơn giản.
Ý tưởng cơ bản đằng sau lập trình động rất đơn giản. Nói chung, để giải quyết một vấn đề nhất định, chúng ta cần giải quyết các phần khác nhau của nó (vấn đề con), và giải quyết các vấn đề con hợp lại để giải quyết vấn đề gốc. Thông thường, nhiều vấn đề con rất giống nhau, vì vậy lập trình động cố gắng chỉ giải quyết mỗi vấn đề con một lần, làm giảm khối lượng tính toán: một khi giải quyết một vấn đề con nhất định đã được tính toán, nó được lưu trữ trong bộ nhớ để trực tiếp kiểm tra khi cần giải quyết một vấn đề con tương tự lần sau.
Những câu hỏi cổ điển nhất về lập kế hoạch động là vấn đề về ba lô.
Các bước của thuật toán:
1, tính cấu trúc tối ưu. Nếu giải pháp của các vấn đề con trong giải pháp tối ưu của vấn đề cũng là tối ưu, chúng ta sẽ gọi vấn đề là có tính cấu trúc tối ưu (tức là đáp ứng các nguyên tắc tối ưu). Tính cấu trúc tối ưu cung cấp các manh mối quan trọng cho giải quyết các vấn đề trong thuật toán lập trình động.
2, tính chất chồng chéo của các vấn đề con. Tính chất chồng chéo của các vấn đề con là khi giải quyết các vấn đề từ trên xuống dưới bằng thuật toán hồi quy, các vấn đề con không phải luôn luôn là vấn đề mới mỗi lần phát sinh, một số vấn đề con sẽ được tính toán nhiều lần. Các thuật toán lập kế hoạch năng động tận dụng tính chất chồng chéo của các vấn đề con, tính toán mỗi vấn đề con một lần và sau đó lưu lại kết quả tính toán của nó trong một bảng, khi cần tính toán các vấn đề con đã được tính toán một lần nữa, chỉ cần xem xét một chút kết quả trong bảng để có hiệu quả cao hơn.
Các thuật toán phân loại Bayesian đơn giản dựa trên định lý Bayesian. Các thuật toán phân loại Bayesian đơn giản dựa trên suy đoán xác suất, đó là làm thế nào để hoàn thành các nhiệm vụ lý luận và quyết định trong trường hợp các điều kiện tồn tại không chắc chắn, chỉ biết khả năng xảy ra của chúng.
Máy phân loại Bayes đơn giản dựa trên mô hình xác suất tự nhiên chính xác, và có thể đạt được hiệu quả phân loại rất tốt trong các tập hợp mẫu có sự giám sát học tập. Trong nhiều ứng dụng thực tế, ước tính các tham số của mô hình Bayes đơn giản sử dụng phương pháp ước tính gần gũi nhất, tức là mô hình Bayes đơn giản hoạt động mà không sử dụng xác suất Bayes hoặc bất kỳ mô hình Bayes nào.
Mặc dù có những ý tưởng đơn giản và giả định đơn giản, các bộ phân loại Bayes đơn giản vẫn có thể hoạt động khá tốt trong nhiều tình huống thực tế phức tạp.