Mười thuật toán thực tế cơ bản mà lập trình viên phải biết và giải thích của chúng

• ### Thuật toán 1: Thuật toán sắp xếp nhanh

Lưu trữ 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 dự án 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ế, lưu trữ nhanh thường nhanh hơn nhiều so với các thuật toán khác bởi vì vòng lặp nội bộ của nó (innerloop) có thể được thực hiện hiệu quả trên hầu hết các cấu trúc.

Lưu trữ nhanh sử dụng Divideandconquer để chia một danh sách thành hai danh sách con.

Bước tính toán:

• 1, chọn một phần tử trong mảng, gọi là pivot,

• 2 , sắp xếp lại số, tất cả các yếu tố nhỏ hơn so với giá trị chuẩn được đặt ở phía trước của chuẩn, tất cả các yếu tố lớn hơn so với giá trị chuẩn được đặt ở phía sau của chuẩn ((tương tự số có thể đi đến bất kỳ bên nào). Sau khi thoát khỏi phân vùng này, chuẩn nằm ở vị trí trung tâm của số.

• 3 Recursively ((recursive) sắp xếp các tiểu số nhỏ hơn các yếu tố chuẩn và các tiểu số lớn hơn các yếu tố chuẩn.

  Trong trường hợp cơ bản nhất của quy trình hồi quy, kích thước của số là 0 hoặc 1, nghĩa là nó đã được sắp xếp tốt mãi mãi. Mặc dù liên tục hồi quy, nhưng thuật toán này sẽ luôn thoát ra, bởi vì trong mỗi lần lặp, nó sẽ đặt ít nhất một phần tử vào vị trí cuối cùng của nó.

• ### Thuật toán 2: Thuật toán sắp xếp hàng loạt

Heapsort là một thuật toán sắp xếp được thiết kế bằng cách sử dụng cấu trúc dữ liệu của Heapsort. Heapsort là một cấu trúc gần giống như một cây nhị phân hoàn toàn, đồng thời đáp ứng tính chất của Heapsort: giá trị khóa hoặc chỉ mục của một node con luôn nhỏ hơn hoặc lớn hơn node cha của nó.

Tính phức tạp thời gian trung bình của các phân loại là O ((nlogn) 。

Bước tính toán:

• 1 , tạo ra một H[0..n-1]

• 2, thay đổi đầu ([maximum]) và cuối

• 3, thu nhỏ kích thước của cột thành 1 và gọi shift_down ((0)), mục đích là để điều chỉnh dữ liệu trên cùng của mảng mới vào vị trí tương ứng

• 4, lặp lại bước 2 cho đến khi khối lượng là 1

• Thuật toán 3: Chuyển tập và sắp xếp

Tham gia sắp xếp (tiếng Anh: Mergesort) là một thuật toán sắp xếp hiệu quả dựa trên hoạt động sáp nhập. Đây là một ứng dụng rất điển hình của DivideandConquer.

Bước tính toán:

• 1, yêu cầu không gian, làm cho kích thước của nó 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ữ chuỗi đã được hợp nhất

• 2 , thiết lập hai con trỏ, vị trí ban đầu là hai vị trí ban đầu của chuỗi đã được sắp xếp

• 3, so sánh hai yếu tố được chỉ ra bởi con trỏ, chọn các yếu tố tương đối nhỏ để đưa vào không gian kết hợp và di chuyển con trỏ đến vị trí tiếp theo

• 4, lặp lại bước 3 cho đến khi một con trỏ đến cuối chuỗi

• 1. Viết 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

• Thuật toán 4: Thuật toán tìm kiếm phân chia

Thuật toán tìm kiếm phân chia là một thuật toán tìm kiếm một phần tử cụ thể trong mảng có trật tự. Quá trình tìm kiếm bắt đầu từ phần tử giữa của mảng và kết thúc nếu phần tử giữa chính xác là phần tử cần tìm; nếu một phần tử cụ thể lớn hơn hoặc nhỏ hơn phần tử giữa, 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ử giữa và bắt đầu so sánh từ phần tử giữa như lúc bắt đầu.

• ### Thuật toán 5: BFPRT

Vấn đề giải quyết của thuật toán BFPRT rất cổ điển, đó là lựa chọn từ một chuỗi các phần tử n một phần tử k lớn nhất (k nhỏ nhất), thông qua phân tích khéo léo, BFPRT có thể đảm bảo độ phức tạp theo thời gian tuyến tính trong trường hợp xấu 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 thuật toán trong trường hợp xấu nhất, vẫn có thể đạt đến độ phức tạp theo thời gian của o (n), năm tác giả thuật toán đã xử lý tinh tế.

Bước tính toán:

• 1, chia n nguyên tố mỗi 5 thành n/5 (bên trên) nhóm.

• 2, lấy số trung bình của mỗi nhóm, cách sắp xếp tùy ý, chẳng hạn như chèn sắp xếp.

• 3, thuật toán chọn gọi lặp đi lặp lại tìm kiếm các số trung bình của tất cả các số trung bình trong bước trước, đặt là x, trong trường hợp có một số số trung bình, chọn một số trung bình nhỏ hơn.

• 4, sử dụng x để phân chia mảng, đặt số ít hơn bằng x là k, số lớn hơn x là n - k.

• 5 , nếu i==k, trả về x; nếu ik, lặp lại tìm kiếm phần tử nhỏ nhất i-k trong các phần tử lớn hơn x.

  Điều kiện kết thúc: khi n = 1, trả về là yếu tố nhỏ i.

• Thuật toán 6: DFS (Trước tiên tìm kiếm độ sâu)

Thuật toán tìm kiếm ưu tiên độ sâu (Depth-First-Search) là một loại thuật toán tìm kiếm. Nó đi theo chiều sâu của cây, tìm các node trong cây, các nhánh của cây càng sâu càng tốt. Khi tất cả các bên của node v đã được tìm kiếm, tìm kiếm sẽ quay trở lại điểm bắt đầu của bên tìm thấy node v.

Tìm kiếm ưu tiên chiều sâu là thuật toán cổ điển trong đồ họa, sử dụng thuật toán tìm kiếm ưu tiên chiều sâu có thể tạo ra bảng sắp xếp topological tương ứng với đồ họa mục tiêu, sử dụng bảng sắp xếp topological có thể dễ dàng giải quyết nhiều vấn đề đồ họa liên quan, chẳng hạn như vấn đề đường dẫn tối đa, v.v.

Các bước của thuật toán được ưu tiên theo chiều sâu:

• 1 , truy cập v;

• 2, bắt đầu từ các điểm tiếp cận chưa được truy cập của v, đi qua các đồ thị với ưu tiên độ sâu; cho đến khi tất cả các đỉnh có đường dẫn tương ứng với v trong đồ thị được truy cập;

• 3, Nếu có đỉnh chưa được truy cập trong bản đồ thời gian này, bắt đầu từ một đỉnh chưa được truy cập, thực hiện lần lượt truy cập ưu tiên độ sâu cho đến khi tất cả các đỉnh trên bản đồ đã được truy cập.

  Những mô tả trên có thể hơi trừu tượng, ví dụ:

  DFS bắt đầu từ một đỉnh v trong biểu đồ truy cập, bắt đầu từ v, truy cập bất kỳ đỉnh tiếp giáp nào của nó là w1; sau đó bắt đầu từ w1, truy cập đỉnh tiếp giáp với w1 nhưng chưa truy cập; và sau đó bắt đầu từ w2, truy cập tương tự, … và tiếp tục như vậy cho đến khi tất cả các đỉnh tiếp giáp được truy cập là u.

  Tiếp theo, quay trở lại một bước và quay trở lại đỉnh mà bạn đã truy cập lần trước để xem liệu có những đỉnh lân cận khác không được truy cập. Nếu có, hãy truy cập đỉnh này và sau đó bắt đầu từ đỉnh này để thực hiện truy cập tương tự như trước; nếu không, hãy quay trở lại một bước nữa để tìm kiếm. Lặp lại quá trình trên cho đến khi tất cả các đỉnh trong bản đồ kết nối đã được truy cập.

• Thuật toán 7: BFS (Broad Foresight Prioritization)

BFS là một thuật toán tìm kiếm đồ họa. Nói một cách đơn giản, BFS là một thuật toán bắt đầu từ các node gốc và đi qua các node trên cây theo chiều rộng của cây. Nếu tất cả các node được truy cập, thuật toán sẽ ngừng hoạt động.

Bước tính toán:

• 1. Đầu tiên, đặt 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 nút con trực tiếp chưa được kiểm tra vào dãy.

• 3 , Nếu hàng không, nghĩa là toàn bộ bản đồ đã được kiểm tra, nghĩa là không có mục tiêu tìm kiếm trong bản đồ.

• 4, lặp lại bước 2.

• Thuật toán tám: Thuật toán Dijkstra

Thuật toán Dijkstra (tiếng Anh: Dijkstra-salgorithm) được đề xuất bởi nhà khoa học máy tính người Hà Lan Eizhel Dijkstra. Thuật toán Dijkstra sử dụng tìm kiếm ưu tiên chiều rộng để giải quyết vấn đề đường ngắn nhất nguồn duy nhất của đồ thị định hướng không âm tính. Thuật toán này thường được sử dụng cho thuật toán định tuyến hoặc làm một mô-đun con cho các thuật toán đồ thị khác.

Lượng đầu vào của thuật toán này bao gồm một đồ thị định hướng có trọng lượng G, và một đỉnh nguồn trong G S. Chúng ta dùng V để biểu thị tập hợp tất cả các đỉnh trong G. Các cạnh trong mỗi đồ thị là một cặp các yếu tố có trật tự được tạo ra bởi hai đỉnh.[0,∞] định nghĩa.

Do đó, w ((u,v) là trọng lượng không âm của đỉnh u đến đỉnh v. trọng lượng của một bên có thể được hình dung là khoảng cách giữa hai đỉnh. trọng lượng của đường đi giữa hai điểm là tổng trọng lượng của tất cả các bên trên đường đi.

Bước tính toán:

• 1, thời điểm ban đầu S = {V0}, T = {các đỉnh khác}, giá trị khoảng cách của đỉnh trong T Nếu có , d(V0,Vi) là trọng số trên đường cong Nếu không có , d (V0,Vi) là

• 2, chọn từ T một đỉnh có giá trị khoảng cách nhỏ nhất là W và không nằm trong S, thêm S

• 3, sửa đổi giá trị khoảng cách của đỉnh trong T còn lại: Nếu thêm W làm đỉnh trung tâm, giá trị khoảng cách từ V0 đến Vi sẽ được sửa đổi

  Lặp lại các bước 2 và 3 ở trên cho đến khi S bao gồm tất cả các đỉnh, tức là W = Vi

• Thuật toán 9: Thuật toán lập trình động

Lập trình động (tiếng Anh: 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ế học để giải quyết các vấn đề phức tạp bằng cách phân tách các vấn đề gốc thành các vấn đề con tương đối đơn giản. Lập trình động thường được áp dụng cho các vấn đề có các vấn đề con chồng lên nhau và cấu trúc tốt nhất, phương pháp lập trình động thường tốn ít thời gian hơn các giải pháp đơn giản.

Ý tưởng cơ bản đằng sau việc lập kế hoạch động rất đơn giản. Nói chung, nếu chúng ta muốn 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í dụ như các vấn đề con), sau đó kết hợp các giải pháp của các vấn đề con để có được giải pháp cho vấn đề ban đầu. Thông thường, nhiều vấn đề con rất giống nhau, vì vậy phương pháp lập kế hoạch động cố gắng giải quyết mỗi vấn đề con chỉ một lần, do đó giảm khối lượng tính toán: một khi giải pháp cho một vấn đề con đã được tính toán, nó sẽ được lưu trữ trong bộ nhớ để lần tiếp theo cần giải quyết cùng một vấn đề con.

Câu hỏi cổ điển nhất về kế hoạch động là vấn đề về ba lô.

Bước tính toán:

Tính cấu trúc tối ưu. Nếu giải pháp tối ưu của vấn đề bao gồm giải pháp cho các vấn đề con cũng là tối ưu, chúng ta sẽ nói rằng vấn đề có tính cấu trúc tối ưu (nghĩa là đáp ứng nguyên tắc tối ưu hóa). Tính cấu trúc tối ưu cung cấp manh mối quan trọng cho việc giải quyết vấn đề bằng thuật toán lập trình động.

Tính chất chồng lên của các vấn đề con. Tính chất chồng lên 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 luân phiên, mỗi lần tạo ra các vấn đề con không phải là vấn đề mới, một số vấn đề con sẽ được tính toán nhiều lần. Thuật toán lập trình động chính là sử dụng tính chất chồng lên của các vấn đề con, chỉ tính toán một lần cho mỗi vấn đề con, sau đó lưu 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 kết quả trong bảng, để có hiệu quả cao hơn.

• ### Thuật toán 10: Thuật toán phân loại Bayes đơn giản

Thuật toán phân loại Bayes đơn giản là một thuật toán phân loại xác suất đơn giản dựa trên định lý của Bayes. Thuật toán phân loại Bayes đơn giản dựa trên suy luận xác suất, đó là làm thế nào để hoàn thành nhiệm vụ suy luận và ra quyết định trong trường hợp không chắc chắn về sự tồn tại của nhiều điều kiện, chỉ biết xác suất của chúng.

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, có thể đạt được hiệu quả phân loại rất tốt trong tập trung mẫu có học giám sát. Trong nhiều ứng dụng thực tế, các tham số mô hình Bayes đơn giản được ước tính bằng phương pháp ước tính gần nhất, có nghĩa là mô hình Bayes đơn giản có thể 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ù với những suy nghĩ ngây thơ và giả định quá đơn giản, bộ phân loại Bayes ngây thơ vẫn có thể đạt được hiệu quả khá tốt trong nhiều tình huống thực tế phức tạp.