Ví dụ về các thuật toán trong Python

Nếu giải quyết vấn đề là một phần trung tâm của khoa học máy tính, thì các giải pháp mà bạn tạo ra thông qua quá trình giải quyết vấn đề cũng rất quan trọng. Trong khoa học máy tính, chúng tôi gọi các giải pháp này là thuật toán. Thuật toán là một danh sách hướng dẫn từng bước mà nếu tuân theo chính xác sẽ giải quyết được vấn đề đang xem xét

Ví dụ: một thuật toán để tính diện tích hình tròn cho biết bán kính của nó có thể trông như thế này

Thuật toán Ví dụ 1 [tiếng Anh]

1. Hỏi bán kính

2. Tính diện tích bằng cách bình phương bán kính và nhân kết quả với số pi

3. Hiển thị khu vực tính toán

Lưu ý rằng thuật toán này bao gồm một tập hợp các bước được đánh số. Nó được viết bằng tiếng Anh, để dễ hiểu. Mặc dù các thuật toán đơn giản có thể dễ dàng hiểu được khi viết bằng tiếng Anh, các thuật toán phức tạp hơn cần ký hiệu chính xác hơn. Để cải thiện độ chính xác, các thuật toán thường được viết bằng mã giả. Mã giả là một ký hiệu chính xác hơn tiếng Anh nhưng nhìn chung không chính xác như ngôn ngữ lập trình. Thuật toán tương tự được biểu thị bằng mã giả có thể trông giống như thế này

Thuật toán Ví dụ 2 [Mã giả]

1. Hỏi bán kính

2. đặt diện tích = [bán kính2] × π

3. Khu vực trưng bày

Lưu ý cách ví dụ mã giả thể hiện bước 2 chính xác hơn, chỉ định công thức theo thuật ngữ toán học

Mục tiêu của chúng tôi trong khoa học máy tính là xử lý một vấn đề và phát triển một thuật toán có thể dùng làm giải pháp chung. Khi chúng tôi có một giải pháp như vậy, chúng tôi có thể sử dụng máy tính của mình để tự động hóa việc thực hiện nó bằng lập trình. Lập trình là một kỹ năng cho phép một nhà khoa học máy tính sử dụng một thuật toán và biểu diễn thuật toán đó dưới dạng một ký hiệu [chương trình] mà máy tính có thể làm theo. Một chương trình được viết bằng một ngôn ngữ lập trình như Python, ngôn ngữ bạn sẽ học trong cuốn sách này

Để giúp bạn hiểu sự khác biệt giữa thuật toán và chương trình, hãy xem xét chương trình này để tính diện tích hình tròn

Chương trình là một thuật toán được thể hiện bằng một ngôn ngữ lập trình. Chúng ta cũng có thể nói rằng chương trình là sự thực hiện của một thuật toán. Trong ví dụ này, cả thuật toán và chương trình đều có ba bước. Bước đầu tiên nhận một số đầu vào từ người dùng và đầu vào vào thứ gì đó mà máy tính có thể làm toán; . Mặc dù chúng tôi chưa đề cập đến bất kỳ chi tiết nào về Python, nhưng hy vọng bạn có thể thấy sự tương ứng giữa các bước của thuật toán mà con người có thể thực hiện [nhưng không được máy tính thực hiện] và các bước của chương trình có thể thực hiện được.

Các thuật toán rất quan trọng vì quá trình giải quyết vấn đề thông qua lập trình thường bắt đầu bằng việc thiết kế một thuật toán. Người lập trình thường diễn đạt thuật toán dưới dạng mã giả, sau đó chuyển thuật toán thành chương trình để máy tính thực hiện. Trong phần tiếp theo, bạn sẽ học cách thực thi chương trình Python trên máy tính

Kiến thức về Cấu trúc dữ liệu và Thuật toán tạo thành cơ sở để xác định các lập trình viên, đưa ra một lý do khác để những người đam mê công nghệ lấy Chứng chỉ Python. Trong khi cấu trúc dữ liệu giúp tổ chức dữ liệu, thuật toán giúp tìm giải pháp cho các vấn đề phân tích dữ liệu không có hồi kết. Vì vậy, nếu bạn vẫn chưa biết về Cấu trúc dữ liệu và thuật toán trong Python, đây là một bài viết chi tiết sẽ giúp bạn hiểu và thực hiện chúng

Trước khi tiếp tục, hãy xem tất cả các chủ đề được thảo luận ở đây

Cấu trúc dữ liệu trong Python

Cấu trúc dữ liệu tích hợp

danh sách. Lưu trữ các phần tử được lập chỉ mục có thể thay đổi và có thể chứa các mục trùng lặp

bộ dữ liệu. Lưu trữ các phần tử được lập chỉ mục, không thể thay đổi có thể có các bản sao trùng lặp

từ điển. Lưu trữ các cặp khóa-giá trị có thể thay đổi

bộ. Chứa các yếu tố duy nhất, không có thứ tự có thể thay đổi

Cấu trúc dữ liệu do người dùng định nghĩa

Mảng. Tương tự như Danh sách, nhưng lưu trữ một loại phần tử

Cây rơm. Cấu trúc dữ liệu LIFO [Last-In-First-Out] tuyến tính

hàng đợi. Cấu trúc dữ liệu FIFO tuyến tính [Nhập trước xuất trước]

Cây. Cấu trúc dữ liệu phi tuyến tính có gốc và các nút

Danh sách liên kết. Cấu trúc dữ liệu tuyến tính được liên kết với con trỏ

đồ thị. Lưu trữ một tập hợp các điểm hoặc nút cùng với các cạnh

Bản đồ băm. Trong Python, Hash Maps giống như Từ điển

Bài viết về Cấu trúc dữ liệu và thuật toán trong Python này sẽ yêu cầu bạn phải có kiến ​​thức trước về Cấu trúc dữ liệu trong Python. Trong trường hợp bạn không có nhiều ý tưởng về nó, bấm vào đây

thuật toán

Thuật toán là gì?

Thuật toán là các quy tắc hoặc hướng dẫn được xây dựng theo thứ tự hữu hạn, tuần tự để giải quyết các vấn đề và nhận được kết quả cần thiết. Chúng cung cấp mã giả cho các vấn đề và có thể được triển khai bằng một số ngôn ngữ vì chúng không dành riêng cho ngôn ngữ

Làm thế nào để bạn viết thuật toán?

Các thuật toán thường được viết dưới dạng kết hợp giữa ngôn ngữ người dùng dễ hiểu và một số ngôn ngữ lập trình phổ biến. Chúng thường được viết ra theo từng bước, tuy nhiên, không phải lúc nào cũng cần thiết phải làm như vậy. Không có quy tắc riêng biệt để xây dựng các thuật toán nhưng bạn sẽ cần ghi nhớ những điểm sau

1. Tìm ra vấn đề chính xác là gì
2. Xác định nơi bạn cần bắt đầu
3. Xác định nơi bạn cần dừng lại
4. Xây dựng các bước trung gian
5. Xem lại các bước của bạn

Ví dụ: nếu bạn phải xây dựng một thuật toán để kiểm tra xem một sinh viên có vượt qua kỳ thi hay không, bạn có thể làm theo các bước đã cho

Bước 1. BẮT ĐẦU

Bước 2. Khai báo hai biến x, y

Bước 3. Lưu trữ các điểm mà học sinh đạt được trong x

Bước 4. Lưu trữ điểm vượt qua tối thiểu trong y

Bước 5. Kiểm tra xem x có lớn hơn hoặc bằng y không. Nếu đúng thì trả về “Đạt” nếu không thì trả về “Không đạt”

Bước 6. DỪNG LẠI

Tuy nhiên bạn có thể thao tác các bước tùy theo sở thích của mình. Chẳng hạn, bạn có thể gán giá trị cho các biến ở chính bước 2 thay vì thực hiện bước 3 và 4. Bằng cách này, một bài toán có thể có nhiều cách giải và tùy thuộc vào bài toán và người lập trình để chọn cách giải khả thi và đáng tin cậy nhất

Các yếu tố của một thuật toán tốt

• Các bước cần phải hữu hạn, rõ ràng và dễ hiểu
• Cần có một mô tả rõ ràng và chính xác về đầu vào và đầu ra
• Mỗi bước cần có một đầu ra xác định chỉ phụ thuộc vào đầu vào trong bước đó hoặc các bước trước đó
• Thuật toán phải đủ linh hoạt để nhào nặn nó để cho phép một số giải pháp
• Các bước nên sử dụng các nguyên tắc cơ bản về lập trình chung và không nên dành riêng cho ngôn ngữ

Các lớp thuật toán

Lớp Mô tả

Phân chia và chinh phục

Chia vấn đề thành các phần phụ và giải quyết từng phần riêng biệt

Lập trình năng động

Chia bài toán thành các phần nhỏ, ghi nhớ kết quả của các phần nhỏ và áp dụng cho các bài tương tự

thuật toán tham lam

Liên quan đến việc thực hiện bước dễ nhất trong khi giải quyết vấn đề mà không phải lo lắng về sự phức tạp của các bước trong tương lai

Tiếp tục với bài viết Cấu trúc dữ liệu và thuật toán trong Python này, chúng ta hãy xem một số thuật toán quan trọng như Thuật toán duyệt cây, Thuật toán tìm kiếm, Thuật toán sắp xếp, v.v.

Thuật toán duyệt cây

Cây trong Python là cấu trúc dữ liệu phi tuyến tính có gốc và các nút như đã đề cập trước đó. Tree Traversal đề cập đến việc truy cập từng nút có trong cây chính xác một lần để cập nhật hoặc kiểm tra chúng. Hãy nhìn vào cái cây được hiển thị bên dưới

Dựa trên thứ tự mà các nút được truy cập, có thể có ba loại duyệt cây

• Truyền tải đơn đặt hàng trước [Gốc-Trái-Phải]
• Truyền tải theo thứ tự [Trái-Gốc-Phải]
• Truyền tải sau đơn hàng [Trái-Phải-Gốc]

Trước khi tạo các hàm cho từng giao dịch này, bạn sẽ cần tạo một lớp Node và tạo cây bằng cách sử dụng đoạn mã sau [Chạy tất cả các hàm cùng với điều này]

# creating a Node class 
class Node:
    def __init__[self,val]:
        self.childleft = None
        self.childright = None
        self.nodedata = val

# Creating an instance of the Node class to construct the tree shown in the image above
root = Node[1]
root.childleft = Node[2]
root.childright = Node[3]
root.childleft.childleft = Node[4]
root.childleft.childright = Node[5]  

duyệt theo thứ tự

Duyệt theo thứ tự đề cập đến việc duyệt qua cây theo cách mà trước tiên bạn truy cập các nút bên trái, sau đó là nút gốc và sau đó là các nút bên phải. Bạn bắt đầu duyệt từ tất cả các nút trong cây con bên trái, sau đó di chuyển về phía gốc và cuối cùng là cây con bên phải

Trong cây hiển thị ở trên, 4 là nút ngoài cùng bên trái và do đó, đây là nút đầu tiên được truy cập. Tiếp theo, bạn di chuyển về phía gốc, vì vậy gốc của nút 4 là 2, do đó bạn truy cập nút 2. Sau đó, bạn phải kiểm tra xem bên phải mình có nút nào không và cây như hình trên, có nút 5 nên nút 5 được thăm. Khi đã xong, cây con bên trái được hoàn thành và sau đó bạn phải tuân theo quy tắc tương tự một lần nữa. e left-root-right để hoàn thành quá trình truyền tải

Thuật toán cho giao dịch theo thứ tự sẽ như sau

Bước 1. Đi qua các nút có trong cây con bên trái

Bước 2. Ghé thăm nút gốc

Bước 3. Đi qua cây con bên phải

chức năng theo thứ tự

def InOrd[root]:
    if root:
        InOrd[root.childleft]
        print [root.nodedata]
        InOrd[root.childright]
InOrd[root]

Khi bạn chạy chức năng này cùng với mã được hiển thị trước đó, bạn sẽ nhận được giao dịch theo thứ tự cho cây nhị phân đã cho

Giao dịch đặt hàng trước

Trong quá trình truyền tải Đơn đặt hàng trước, nút gốc được truy cập trước, tiếp theo là cây con bên trái và sau đó là cây con bên phải. Vì vậy, trong ví dụ trên, trước tiên bạn truy cập nút 1, sau đó là nút 2 mà chúng tôi hướng về bên trái của nút 1. Sau đó, bạn phải di chuyển về phía bên trái của nút 2 và truy cập nút 4, sau đó là nút 5. Với điều này, gốc và cây con bên trái đã được thực hiện và do đó, bạn cần truy cập vào cây con bên phải

Thuật toán để duyệt đơn đặt hàng trước sẽ như sau

Bước 1. Ghé thăm nút gốc

Bước 2. Đi qua các nút có trong cây con bên trái

Bước 3. Đi qua cây con bên phải

Chức năng đặt hàng trước

def PreOrd[root]:
    if root:
        print [root.nodedata]
        PreOrd[root.childleft]
        PreOrd[root.childright]
PreOrd[root]

Tra cứu sau khi đặt hàng

Quá trình duyệt theo thứ tự sau bắt đầu từ bên trái rồi sang bên phải và cuối cùng là gốc. Trong ví dụ trên, bạn truy cập vào nút 4 sau đó di chuyển sang phải tới nút 5. Khi đã xong, bạn phải truy cập thư mục gốc i. nút điện tử 2. Với điều này, cây con bên trái đã hoàn tất, vì vậy bạn cần chuyển sang cây con bên phải và cuối cùng truy cập vào gốc

Thuật toán cho Post-order travers sẽ như sau

Bước 1. Đi qua các nút có trong cây con bên trái

Bước 2. Đi qua cây con bên phải

Bước 3. Ghé thăm nút gốc

Chức năng đặt hàng sau

def PostOrd[root]:
    if root:
        PostOrd[root.childleft]
        PostOrd[root.childright]
        print [root.nodedata]
PostOrd[root]

Sắp xếp dữ liệu là một vấn đề thời gian thực và cần một số thuật toán sắp xếp để giải quyết. Vì vậy, hãy tiếp tục với bài viết Cấu trúc dữ liệu và thuật toán trong Python này, chúng ta hãy tìm hiểu sâu về Thuật toán sắp xếp trong Python

thuật toán sắp xếp

Các thuật toán sắp xếp được sử dụng để sắp xếp dữ liệu theo một số thứ tự nhất định. Các thuật toán sắp xếp có thể được phân thành năm loại đó là

• Hợp nhất Sắp xếp
• Sắp xếp bong bóng
• Sắp xếp chèn
• Sắp xếp lựa chọn
• Sắp xếp vỏ

Ghi chú. Tất cả các thuật toán ở đây được sắp xếp theo thứ tự tăng dần

Hợp nhất Sắp xếp

Thuật toán Sắp xếp hợp nhất tuân theo quy tắc Chia để trị. Ở đây, danh sách các mục đã cho trước tiên được chia thành các danh sách nhỏ hơn cho đến khi đạt đến điểm mà mỗi danh sách bao gồm chính xác một mục. Theo mặc định, một danh sách bao gồm một mục sẽ được sắp xếp và thuật toán sắp xếp hợp nhất sau đó so sánh các danh sách liền kề và sắp xếp lại chúng theo trình tự mong muốn. Quá trình này được thực hiện đệ quy cho đến khi đạt đến điểm chỉ tồn tại một danh sách được sắp xếp

Hợp nhất thuật toán sắp xếp

Bước 1. Kiểm tra xem danh sách có chứa nhiều mục không;

Bước 2. Danh sách sẽ được chia nhiều lần cho đến khi chỉ còn lại một phần tử trong mỗi danh sách con

Bước 3. Hợp nhất đệ quy các danh sách con bằng cách sắp xếp chúng theo thứ tự nhất định cho đến khi bạn nhận được một danh sách được sắp xếp duy nhất

Hợp nhất chương trình Sắp xếp

def msort[mylist, left, right]:
    if right - left > 1:
        middle = [left + right]//2
        msort[mylist, left, middle]
        msort[mylist, middle, right]
        mlist[mylist, left, middle, right]

def mlist[mylist, left, middle, right]:
    leftlist = mylist[left:middle]
    rightlist = mylist[middle:right]
    k = left
    i = 0
    j = 0
    while [left + i < middle and middle + j < right]:
        if [leftlist[i] a[y+1]:
                a[y],a[y+1]=a[y+1],a[y]
    return a
a=[3,6,1,8]
bs[a]
    

ĐẦU RA. [1, 3, 6, 8]

Chương trình trên sẽ sắp xếp một danh sách đã cho theo thứ tự tăng dần

Sắp xếp chèn

Sắp xếp chèn chọn một phần tử của danh sách đã cho tại một thời điểm và đặt nó vào vị trí chính xác mà nó sẽ được đặt

Thuật toán sắp xếp chèn

Bước 1. So sánh phần tử đầu tiên với phần tử tiếp theo [phím] và nếu phần tử bên trái và phần tử chính không theo thứ tự, hãy hoán đổi chúng

Bước 2. Lấy phần tử tiếp theo [khóa] và nếu phần tử khóa mới cần được định vị lại, hãy dịch chuyển các phần tử của danh sách đã sắp xếp sang bên phải cho đến khi một vị trí thích hợp được tạo cho phần tử đang được xem xét

Bước 3. Lặp lại bước 2 cho đến khi tất cả các phần tử của danh sách đã cho được sắp xếp

Chương trình sắp xếp chèn

def isort[a]: 
    for x in range[1, len[a]]: 
        k = a[x]  #element present at index number 1
        j = x-1
        while j >=0 and k < a[j] :      #comparing elements with the next until the last item 
                a[j+1] = a[j] 
                j -= 1         #comparing each element to the elements present to its left 
        a[j+1] = k     #new item becomes the key

a = [24, 56, 1, 50, 17] 
isort[a] 
print[a]
  

ĐẦU RA. [1, 17, 24, 50, 56]

Trong chương trình trên, phần tử khóa đầu tiên sẽ là 56 và phần tử này được so sánh với 24, phần tử đầu tiên của danh sách. Vì hai phần tử này đã được sắp xếp, thuật toán chấp nhận phần tử tiếp theo i. e 1 và đây trở thành khóa mới. Vì 1 nhỏ hơn 24 và 56 nên cả 24 và 56 đều dịch chuyển sang phải và 1 được đặt ở đầu mảng. Quy trình tương tự được lặp lại cho đến khi tất cả các mục có trong mảng đã cho được sắp xếp

Sắp xếp lựa chọn

Thuật toán Sắp xếp lựa chọn chia danh sách đã cho thành hai nửa trong đó nửa đầu sẽ là danh sách đã sắp xếp và nửa thứ hai là danh sách chưa sắp xếp. Lúc đầu, danh sách đã sắp xếp trống và tất cả các phần tử cần sắp xếp đều có trong danh sách chưa sắp xếp

Thuật toán Sắp xếp lựa chọn sẽ xem xét tất cả các phần tử có trong danh sách chưa sắp xếp, chọn phần tử được cho là xuất hiện trước rồi đặt nó vào danh sách đã sắp xếp. Sau đó, nó lặp lại quá trình tìm kiếm và đặt phần tử tiếp theo bên phải phần tử đầu tiên trong danh sách đã sắp xếp

Ví dụ: nếu bạn phải sắp xếp các phần tử theo thứ tự tăng dần, thuật toán sắp xếp lựa chọn sẽ xem danh sách đầy đủ, chọn phần tử nhỏ nhất rồi đặt phần tử đó làm phần tử đầu tiên trong danh sách được sắp xếp. Sau đó, nó tìm kiếm phần tử nhỏ nhất tiếp theo và đặt nó ở bên phải phần tử đầu tiên, v.v.

Thuật toán sắp xếp lựa chọn

Bước 1. Đặt phần tử đầu tiên ở mức tối thiểu và so sánh nó với phần tử tiếp theo. Nếu phần tử tiếp theo nhỏ hơn phần tử đã chọn, hãy đánh dấu phần tử đó là phần tử nhỏ nhất và so sánh nó với phần tử tiếp theo. Lặp lại quy trình tương tự cho đến khi bạn so sánh tất cả các phần tử của danh sách chưa sắp xếp

Bước 2. Đặt giá trị nhỏ nhất trong mảng đã sắp xếp [Phần tử này trở thành phần tử đầu tiên của mảng đã sắp xếp]

Bước 3. Tăng vị trí của bộ đếm để trỏ đến phần tử đầu tiên của mảng chưa sắp xếp và lặp lại bước 1 và 2 cho tất cả các phần tử của mảng chưa sắp xếp

Chương trình sắp xếp lựa chọn

def selsort[myarray, r]:
    for x in range[r]:
        minimum = x      #first element is assumed to be the minimum
        for y in range[x + 1, r]:    
            if myarray[y] < myarray[minimum]:     #comparing minimum with the next element
                minimum = y
        [myarray[x], myarray[minimum]] = [myarray[minimum], myarray[x]] #swap elements if required
mylist = [34, 23, 1, 67, 4]
r = len[mylist]
selsort[mylist, r]
print[mylist]

ĐẦU RA. [1, 4, 23, 34, 67]

Sắp xếp vỏ

Thuật toán sắp xếp Shell cho phép bạn sắp xếp các phần tử cách xa nhau. Dãy ban đầu để sắp xếp các phần tử như sau n/ 2, n/4, …, 1 dãy trong đó n là số phần tử có trong danh sách chưa sắp xếp. Ví dụ bạn có một danh sách gồm 8 phần tử thì độ dài của danh sách đó sẽ chia cho 2. e 8/ 2 = 4. Bây giờ, phần tử đầu tiên sẽ được so sánh với phần tử có ở chỉ số 4 và sau đó, khoảng cách sẽ được tạo ra bằng cách chia 8 cho 4. Lúc này, khoảng cách sẽ là 2 và các phần tử nằm trong các khoảng này sẽ được so sánh. Cuối cùng, 8/ 8 = 1 nên các phần tử liền kề sẽ được so sánh và sắp xếp. [Đối với danh sách số lẻ, phần nguyên của thương sẽ được lấy làm khoảng cách]

Thuật toán sắp xếp Shell

Bước 1. Tìm giá trị của khoảng trống bằng cách chia số phần tử cho 2

Bước 2. Chia mảng đã cho thành các mảng con nhỏ hơn có các khoảng cách bằng nhau

Bước 3. Sử dụng sắp xếp chèn, sắp xếp các mảng con

Bước 4. Lặp lại các bước 1, 2 và 3 cho đến khi mảng hoàn chỉnh được sắp xếp

Chương trình sắp xếp vỏ

________số 8

ĐẦU RA. [1, 2, 12, 13, 17, 23, 45]

Tiếp tục với bài viết Cấu trúc dữ liệu và thuật toán trong Python này, chúng ta hãy xem một số thuật toán tìm kiếm quan trọng nhất trong Python

thuật toán tìm kiếm

Các thuật toán tìm kiếm được sử dụng để tìm kiếm hoặc tìm nạp một số phần tử có trong một số tập dữ liệu nhất định. Có nhiều loại thuật toán tìm kiếm như Tìm kiếm tuyến tính, Tìm kiếm nhị phân, Tìm kiếm theo hàm mũ, Tìm kiếm nội suy, v.v.

Tìm kiếm tuyến tính

Thuật toán Tìm kiếm tuyến tính được sử dụng để tìm kiếm liên tiếp một phần tử đã cho bằng cách so sánh nó với từng phần tử của mảng đã cho. Đây là một trong những thuật toán tìm kiếm đơn giản nhất nhưng rất quan trọng để hiểu các thuật toán sắp xếp khác

Thuật toán tìm kiếm tuyến tính

Bước 1. Tạo một hàm sẽ chấp nhận danh sách dữ liệu, độ dài của danh sách và phần tử chính

Bước 2. Nếu một phần tử có trong danh sách đã cho khớp với phần tử chính, hãy trả về số chỉ mục tương ứng

Bước 3. Nếu không tìm thấy phần tử, trả về -1

Chương trình tìm kiếm tuyến tính

def lin_search[myarray, n, key]: 
  
    for x in range[0, n]: 
        if [myarray[x] == key]: 
            return x 
    return -1
  
myarray = [ 12, 1, 34, 17]
key = 17
n = len[myarray]
matched = lin_search[myarray, n, key] 
if[matched == -1]: 
    print["Key is not present"] 
else: 
    print["Key is present in the given list at index", matched]

ĐẦU RA. Khóa có mặt trong danh sách đã cho ở chỉ mục 3

Tìm kiếm nhị phân

Tìm kiếm nhị phân được sử dụng để tìm kiếm một số phần tử đã cho trong một mảng được sắp xếp bằng cách sử dụng Thuật toán giảm và chinh phục. Ở đây, khóa được tìm kiếm bằng cách so sánh nó với phần tử ở giữa và sau đó chia mảng thành một nửa. Nửa bên trái được tìm nếu phần tử cần tìm nhỏ hơn phần tử ở giữa và ngược lại. Các mảng con thích hợp lại được chia thành một nửa và quá trình này được lặp lại một lần nữa

Ví dụ: nếu bạn có một danh sách được sắp xếp gồm 8 phần tử, phần tử chính sẽ được so sánh với phần tử có mặt ở giữa hoặc 7/ 2 = 3. 5 [7 là giá trị chỉ số của phần tử cuối cùng] và giá trị số nguyên được lấy để so sánh. Vì vậy, phần tử chính sẽ được so sánh với giá trị hiện tại ở chỉ mục số 3 và nếu giá trị đã cho nhỏ hơn, quá trình tương tự được lặp lại đối với phía bên trái của phần tử ở giữa và ngược lại

Thuật toán tìm kiếm nhị phân

Bước 1. So sánh khóa với phần tử ở giữa

Bước 2. Nếu khớp, trả về giá trị chỉ số ở giữa

Bước 3. Nếu phần tử khóa lớn hơn phần tử ở giữa, hãy tìm phần tử khóa ở bên phải phần tử ở giữa, ngược lại tìm ở bên trái phần tử đó

Chương trình tìm kiếm nhị phân

def InOrd[root]:
    if root:
        InOrd[root.childleft]
        print [root.nodedata]
        InOrd[root.childright]
InOrd[root]

0

ĐẦU RA.  

Đúng
Sai

Chủ đề cuối cùng được thảo luận trong bài viết Cấu trúc dữ liệu và thuật toán trong Python là Phân tích thuật toán

Phân tích thuật toán

Các thuật toán có thể được phân tích cả trước và sau khi thực hiện. Những phân tích này được gọi là Phân tích tiên nghiệm và Phân tích hậu nghiệm

Phân tích tiên nghiệm [Phân tích lý thuyết]. Hiệu quả của thuật toán được đo bằng cách giả định rằng tất cả các yếu tố khác là không đổi và không ảnh hưởng đến việc thực hiện thuật toán

Phân tích Hậu quả [Phân tích Thực nghiệm]. Các thuật toán sau khi được thực hiện bằng ngôn ngữ lập trình nào đó, sẽ được thực thi trên máy tính nào đó. Vì vậy, trong phân tích này, các giá trị thực tế như độ phức tạp thời gian hoặc thời gian thực hiện của thuật toán cho đến khi nó hoàn thành nhiệm vụ, độ phức tạp không gian hoặc không gian mà thuật toán yêu cầu cho toàn bộ vòng đời của nó, v.v.

Tôi hy vọng bạn rõ ràng với tất cả những gì đã được chia sẻ với bạn trong hướng dẫn này. Điều này đưa chúng ta đến phần cuối của bài viết về Cấu trúc dữ liệu và thuật toán trong Python. Hãy chắc chắn rằng bạn thực hành càng nhiều càng tốt và hoàn nguyên kinh nghiệm của bạn.   

Có một câu hỏi cho chúng tôi?

Để có kiến ​​thức chuyên sâu về Python cùng với các ứng dụng khác nhau của nó, bạn có thể đăng ký tham gia khóa đào tạo trực tuyến về Python trực tiếp với sự hỗ trợ 24/7 và quyền truy cập trọn đời.  

Các thuật toán được sử dụng trong Python là gì?

Các ví dụ về thuật toán là gì?

Làm thế nào để viết một ví dụ thuật toán?

Làm thế nào để học các thuật toán trong Python?