Cấu trúc dữ liệu và thuật toán trong Python javatpoint

Thuật toán là một quy trình từng bước xác định một tập hợp các hướng dẫn phải được thực hiện theo một thứ tự cụ thể để tạo ra kết quả mong muốn. Các thuật toán thường được phát triển độc lập với các ngôn ngữ cơ bản, điều đó có nghĩa là một thuật toán có thể được triển khai bằng nhiều ngôn ngữ lập trình. Tính rõ ràng, độ mịn, hiệu quả và tính độc lập về ngôn ngữ là một số đặc điểm của thuật toán. Khả năng mở rộng và hiệu suất của một thuật toán là những yếu tố chính góp phần vào tầm quan trọng của nó.  

Khái niệm cơ bản đến nâng cao - Tìm hiểu tất cả - Đảm bảo

Thuật toán là gì?

• Thuật toán là một tập hợp các lệnh mà máy tính phải tuân theo để thực hiện các phép tính hoặc các hoạt động giải quyết vấn đề khác
• Theo định nghĩa chính thức của nó, một thuật toán là một tập hợp hữu hạn các hướng dẫn được thực hiện theo một thứ tự cụ thể để thực hiện một nhiệm vụ cụ thể.  
• Nó không phải là toàn bộ chương trình hoặc mã;

• Vấn đề. Một vấn đề có thể được định nghĩa là một vấn đề trong thế giới thực hoặc vấn đề ví dụ trong thế giới thực mà bạn cần phát triển một chương trình hoặc bộ hướng dẫn. Một thuật toán là một tập hợp các hướng dẫn.  
• thuật toán. Một thuật toán được định nghĩa là một quy trình từng bước sẽ được thiết kế cho một vấn đề
• Đầu vào. Sau khi thiết kế một thuật toán, thuật toán được cung cấp các đầu vào cần thiết và mong muốn
• Đơn vị xử lý. Đầu vào sẽ được chuyển đến bộ phận xử lý, tạo ra đầu ra mong muốn
• đầu ra. Kết quả hoặc kết quả của chương trình được gọi là đầu ra

Sau khi xác định thuật toán là gì, bây giờ bạn sẽ xem xét các đặc điểm của thuật toán

Đặc điểm của một thuật toán

Một thuật toán có các đặc điểm sau

• Đầu vào. Một thuật toán yêu cầu một số giá trị đầu vào. Một thuật toán có thể được cung cấp một giá trị khác 0 làm đầu vào
• đầu ra. Khi kết thúc thuật toán, bạn sẽ có một hoặc nhiều kết quả
• sự rõ ràng. Một thuật toán hoàn hảo được định nghĩa là rõ ràng, có nghĩa là các hướng dẫn của nó phải rõ ràng và dễ hiểu
• sự hữu hạn. Một thuật toán phải hữu hạn. Tính hữu hạn trong ngữ cảnh này có nghĩa là thuật toán phải có một số hướng dẫn giới hạn, tức là. e. , các hướng dẫn nên được đếm
• hiệu quả. Bởi vì mỗi hướng dẫn trong một thuật toán ảnh hưởng đến toàn bộ quá trình, nên nó phải phù hợp
• độc lập về ngôn ngữ. Một thuật toán phải độc lập với ngôn ngữ, có nghĩa là các hướng dẫn của nó có thể được thực hiện bằng bất kỳ ngôn ngữ nào và tạo ra kết quả tương tự

Tiếp tục trong hướng dẫn Thuật toán là gì, bạn sẽ xem tại sao bạn cần một thuật toán

Tại sao bạn cần một thuật toán?

Bạn yêu cầu các thuật toán vì những lý do sau

khả năng mở rộng

Nó hỗ trợ bạn hiểu về khả năng mở rộng. Khi bạn gặp một vấn đề lớn trong thế giới thực, bạn phải chia nó thành các bước nhỏ để phân tích nhanh chóng

Màn biểu diễn

Thế giới thực là thách thức để chia thành các bước nhỏ hơn. Nếu một vấn đề có thể dễ dàng chia thành các bước nhỏ hơn, điều đó cho thấy vấn đề đó khả thi

Sau khi hiểu thuật toán là gì, tại sao bạn cần một thuật toán, bạn sẽ xem cách viết một thuật toán bằng một ví dụ

Khởi động sự nghiệp Blockchain của bạn sau sáu tháng

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

• Không có tiêu chuẩn rõ ràng để viết thuật toán. Tuy nhiên, đó là một vấn đề phụ thuộc vào tài nguyên. Các thuật toán không bao giờ được viết với một ngôn ngữ lập trình cụ thể
• Như các bạn đã biết, các cấu trúc mã cơ bản chẳng hạn như vòng lặp do, for, while, tất cả các ngôn ngữ lập trình đều chia sẻ điều khiển luồng như if-else, v.v. Một thuật toán có thể được viết bằng cách sử dụng các cấu trúc phổ biến này
• Các thuật toán thường được viết theo kiểu từng bước, nhưng điều này không phải lúc nào cũng đúng. Viết thuật toán là một quá trình xảy ra sau khi miền vấn đề đã được xác định rõ. Đó là, bạn phải nhận thức được miền vấn đề mà bạn đang phát triển giải pháp

Thí dụ

Bây giờ, sử dụng một ví dụ để tìm hiểu cách viết thuật toán

Vấn đề. Tạo thuật toán nhân hai số và hiển thị kết quả

Bước 1 - Bắt đầu

Bước 2 – khai báo ba số nguyên x, y & z

Bước 3 - xác định giá trị của x & y

Bước 4 - nhân các giá trị của x & y

Bước 5 - lưu trữ kết quả của bước 4 đến z

Bước 6 - in z

Bước 7 - Dừng lại

Thuật toán hướng dẫn lập trình viên cách viết mã. Ngoài ra, thuật toán có thể được viết dưới dạng

Bước 1 - Bắt đầu mul

Bước 2 - nhận các giá trị của x & y

Bước 3 − z ← x * y

Bước 4 – hiển thị z

Bước 5 - Dừng lại

Trong thiết kế và phân tích thuật toán, phương pháp thứ hai thường được sử dụng để mô tả thuật toán. Nó cho phép nhà phân tích phân tích thuật toán trong khi bỏ qua tất cả các định nghĩa không mong muốn một cách dễ dàng. Họ có thể xem hoạt động nào đang được sử dụng và quy trình đang tiến triển như thế nào. Nó là tùy chọn để viết số bước. Để giải quyết một vấn đề nhất định, bạn tạo một thuật toán. Một vấn đề có thể được giải quyết theo nhiều cách khác nhau

Kết quả là, nhiều thuật toán giải quyết cho một vấn đề nhất định có thể được rút ra. Bước tiếp theo là đánh giá các thuật toán giải pháp được đề xuất và thực hiện giải pháp phù hợp nhất

Khi bạn hoàn thành phần hướng dẫn "Thuật toán là gì" này, bạn sẽ tìm hiểu về một số thành phần của thuật toán

Tìm hiểu Ins & Outs của phát triển phần mềm

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

Sau đây là các yếu tố cần xem xét khi thiết kế một thuật toán

• tính mô đun. Tính năng này được thiết kế hoàn hảo cho thuật toán nếu bạn gặp một vấn đề và chia nó thành các mô-đun nhỏ-nhỏ hoặc các bước nhỏ-nhỏ, đây là định nghĩa cơ bản của thuật toán
• tính đúng đắn. Tính chính xác của thuật toán được định nghĩa là khi các đầu vào đã cho tạo ra đầu ra mong muốn, cho biết rằng thuật toán đã được thiết kế chính xác. Một phân tích của thuật toán đã được hoàn thành một cách chính xác
• khả năng bảo trì. Điều đó có nghĩa là thuật toán nên được thiết kế theo cách đơn giản, có cấu trúc để khi bạn xác định lại thuật toán, không có thay đổi đáng kể nào được thực hiện đối với thuật toán
• chức năng. Nó tính đến các bước hợp lý khác nhau để giải quyết vấn đề trong thế giới thực
• mạnh mẽ. Mạnh mẽ đề cập đến khả năng của một thuật toán để xác định vấn đề của bạn một cách rõ ràng
• Thân thiện với người dùng. Nếu thuật toán khó hiểu, người thiết kế sẽ không giải thích cho người lập trình
• Sự đơn giản. Nếu một thuật toán đơn giản, thì nó cũng đơn giản để hiểu
• khả năng mở rộng. Thuật toán của bạn có thể mở rộng nếu một nhà thiết kế hoặc lập trình viên thuật toán khác muốn sử dụng nó

Bây giờ bạn sẽ thấy tại sao một thuật toán lại cần thiết như vậy sau khi hiểu một số thành phần của nó

Tầm quan trọng của một thuật toán

Có hai yếu tố trong đó thuật toán là cơ bản

Ý nghĩa lý thuyết

Khi bạn gặp một vấn đề trong thế giới thực, bạn phải chia nó thành các mô-đun nhỏ hơn. Để giải cấu trúc vấn đề, trước tiên bạn phải hiểu tất cả các khía cạnh lý thuyết của nó

Ý nghĩa thực tiễn

Như các bạn đã biết, lý thuyết không thể hoàn thiện nếu không có ứng dụng thực tế. Do đó, ý nghĩa của thuật toán có thể được xem xét cả về mặt lý thuyết và thực tiễn

Khi bạn xem qua phần hướng dẫn "thuật toán là gì" này, bạn sẽ thấy các cách tiếp cận của thuật toán

Cách tiếp cận của một thuật toán

Sau khi xem xét cả tầm quan trọng về mặt lý thuyết và thực tiễn của việc thiết kế một thuật toán, các phương pháp sau đã được sử dụng

• Thuật toán vét cạn

Thuật toán này sử dụng cấu trúc logic chung để thiết kế một thuật toán. Nó còn được gọi là thuật toán tìm kiếm toàn diện vì nó loại bỏ tất cả các khả năng để cung cấp giải pháp cần thiết. Có hai loại thuật toán như vậy

1. tối ưu hóa. Việc tìm kiếm tất cả các giải pháp có thể cho một vấn đề và sau đó chọn giải pháp tốt nhất sẽ chấm dứt nếu giải pháp tốt nhất đã được biết
2. hy sinh. Nó sẽ dừng ngay khi giải pháp tốt nhất được tìm thấy

• Phân chia và chinh phục

Đây là một triển khai thuật toán đơn giản. Nó cho phép bạn tạo một thuật toán theo kiểu từng bước. Nó giải cấu trúc thuật toán để giải quyết vấn đề theo nhiều cách khác nhau. Nó cho phép bạn chia vấn đề thành các phương pháp khác nhau, tạo đầu ra hợp lệ cho đầu vào hợp lệ. Đầu ra chính xác này được chuyển tiếp đến chức năng khác

• thuật toán tham lam

Đây là một mô hình thuật toán đưa ra lựa chọn tốt nhất có thể trên mỗi lần lặp với hy vọng chọn được giải pháp tốt nhất. Nó đơn giản để thiết lập và có thời gian thực hiện ngắn hơn. Tuy nhiên, có rất ít trường hợp nó là giải pháp tốt nhất

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

Nó cải thiện hiệu quả của thuật toán bằng cách lưu trữ các kết quả trung gian. Nó trải qua năm bước để tìm ra giải pháp tốt nhất cho vấn đề

1. Nó chia vấn đề thành các vấn đề con để tìm giải pháp tốt nhất
2. Sau khi chia nhỏ bài toán thành các bài toán con, nó sẽ tìm ra lời giải tốt nhất từ ​​các bài toán con này.
3. Ghi nhớ là quá trình lưu trữ kết quả của các bài toán con
4. Sử dụng lại kết quả để ngăn không cho nó được tính toán lại cho cùng các bài toán con
5. Cuối cùng, nó tính toán đầu ra của chương trình phức tạp

• Thuật toán rẽ nhánh và ràng buộc

Chỉ có thể giải các bài toán lập trình số nguyên bằng thuật toán rẽ nhánh và ràng buộc. Phương pháp này chia tất cả các tập nghiệm khả thi thành các tập con nhỏ hơn. Các tập hợp con này sau đó được đánh giá thêm để tìm ra giải pháp tốt nhất

• Thuật toán ngẫu nhiên

Như với một thuật toán tiêu chuẩn, bạn có đầu vào và đầu ra được xác định trước. Các thuật toán xác định có một tập hợp thông tin và kết quả được xác định và tuân theo một số bước được mô tả. Chúng hiệu quả hơn các thuật toán không xác định

• quay lui

Đây là một thủ tục thuật toán đệ quy và loại bỏ giải pháp nếu nó không thỏa mãn các ràng buộc của vấn đề

Theo hiểu biết của bạn về thuật toán là gì và cách tiếp cận của nó, bây giờ bạn sẽ xem xét phân tích thuật toán

Đây là cách để có được công việc nhà phát triển phần mềm hàng đầu

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

Thuật toán có thể được kiểm tra ở hai cấp độ. trước và sau khi nó được tạo ra. Hai phân tích thuật toán như sau

• Phân tích tiên nghiệm

Trong bối cảnh này, phân tích tiên nghiệm đề cập đến phân tích lý thuyết của một thuật toán được thực hiện trước khi thực hiện thuật toán. Trước khi triển khai thuật toán, có thể xem xét các yếu tố khác nhau như tốc độ bộ xử lý, không ảnh hưởng đến việc triển khai

• Phân tích sau

Trong bối cảnh này, phân tích sau đề cập đến một phân tích thực tế của một thuật toán. Thuật toán được thực hiện trên bất kỳ ngôn ngữ lập trình nào để thực hiện nghiên cứu thực nghiệm. Phân tích này xác định cần bao nhiêu thời gian và không gian chạy

Tiếp tục trong hướng dẫn "thuật toán là gì" này, bây giờ bạn sẽ xem xét độ phức tạp của một thuật toán

Độ phức tạp của một thuật toán

Hiệu suất của thuật toán có thể được đo lường theo hai cách

Thời gian phức tạp

Lượng thời gian cần thiết để hoàn thành việc thực hiện thuật toán được gọi là độ phức tạp thời gian. Ký hiệu O lớn được sử dụng để biểu thị độ phức tạp về thời gian của thuật toán. Ký hiệu tiệm cận để mô tả độ phức tạp của thời gian, trong trường hợp này, là ký hiệu O lớn. Độ phức tạp về thời gian được tính chủ yếu bằng cách đếm số bước cần thiết để hoàn thành việc thực hiện. Chúng ta hãy xem một ví dụ về độ phức tạp của thời gian

mu = 1;

// Giả sử bạn phải tính phép nhân n số.   

cho i=1 đến n

mul = mul *1;

// khi vòng lặp kết thúc thì mul giữ phép nhân n số

trả lại mul;

Độ phức tạp về thời gian của câu lệnh lặp trong đoạn mã trước ít nhất là n và khi giá trị của n tăng lên thì độ phức tạp về thời gian cũng tăng theo. Trong khi sự phức tạp của mã, tôi. e. , trả về mul, sẽ không đổi vì giá trị của nó không phụ thuộc vào tầm quan trọng của n và sẽ cung cấp kết quả trong một bước. Độ phức tạp thời gian tồi tệ nhất thường được xem xét vì đó là thời gian tối đa cần thiết cho bất kỳ kích thước đầu vào nhất định nào

Độ phức tạp không gian

Lượng không gian mà một thuật toán yêu cầu để giải một bài toán và tạo ra kết quả được gọi là độ phức tạp không gian của nó. Độ phức tạp của không gian, cũng như độ phức tạp của thời gian, được thể hiện bằng ký hiệu O lớn

Không gian là cần thiết cho một thuật toán vì những lý do sau

1. Để lưu trữ hướng dẫn chương trình
2. Để lưu trữ theo dõi các giá trị không đổi
3. Để lưu trữ theo dõi các giá trị biến
4. Để lưu theo dõi các lệnh gọi hàm, câu lệnh nhảy, v.v.

Độ phức tạp của không gian = Không gian phụ + Kích thước đầu vào

Cuối cùng, sau khi hiểu thuật toán là gì, phân tích và cách tiếp cận của nó, bạn sẽ xem xét các loại thuật toán khác nhau

Các loại thuật toán

Có hai loại thuật toán

• thuật toán tìm kiếm
• thuật toán sắp xếp

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

Mỗi ngày, bạn tìm kiếm một cái gì đó trong cuộc sống hàng ngày của bạn. Tương tự, trong trường hợp máy tính, một lượng lớn dữ liệu được lưu trữ trong máy tính và bất cứ khi nào người dùng yêu cầu dữ liệu, máy tính sẽ tìm kiếm dữ liệu đó trong bộ nhớ và trả lại cho người dùng. Có hai phương pháp chủ yếu để tìm kiếm dữ liệu trong một mảng

Thuật toán tìm kiếm có hai loại

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

Tìm kiếm tuyến tính là một thuật toán đơn giản bắt đầu tìm kiếm một phần tử hoặc một giá trị ở đầu mảng và tiếp tục cho đến khi không tìm thấy phần tử cần thiết. Nó so sánh phần tử cần tìm với tất cả các phần tử trong một mảng; . Thuật toán này có thể được áp dụng cho một danh sách chưa được sắp xếp

• Tìm kiếm nhị phân

Thuật toán nhị phân là thuật toán cơ bản nhất và nó tìm kiếm các phần tử rất nhanh. Nó được sử dụng để tìm một phần tử trong một danh sách được sắp xếp. Để thực hiện thuật toán nhị phân, các phần tử phải được lưu trữ theo thứ tự tuần tự hoặc được sắp xếp. Nếu các phần tử được lưu trữ ngẫu nhiên, tìm kiếm nhị phân không thể thực hiện được

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

Thuật toán sắp xếp sắp xếp lại các phần tử trong một mảng hoặc một cấu trúc dữ liệu nhất định theo thứ tự tăng dần hoặc giảm dần. Toán tử so sánh quyết định thứ tự mới của các phần tử

Bây giờ bạn đã hoàn thành hướng dẫn về "thuật toán là gì", bạn sẽ tóm tắt những gì bạn đã học cho đến nay

Có được nền tảng vững chắc về Java, ngôn ngữ lập trình được sử dụng phổ biến nhất trong phát triển phần mềm với Khóa đào tạo cấp chứng chỉ Java

Bước tiếp theo

Trong hướng dẫn này, bạn đã học thuật toán là gì và đặc điểm của nó là gì. Sau đó, bạn đã xem tại sao bạn cần thuật toán, cách viết chúng và tầm quan trọng của chúng. Sau khi bạn tìm hiểu về các cách tiếp cận và các yếu tố của thuật toán, bạn đã tìm hiểu về độ phức tạp và các loại thuật toán

Giả sử bạn đang tìm kiếm một nghiên cứu sâu rộng hơn, vượt ra ngoài Phát triển phần mềm và bao gồm các khả năng và ngôn ngữ lập trình được yêu cầu nhiều nhất hiện nay. Trong trường hợp đó, Full Stack Java Developer Master's Program của Simplilearn là lựa chọn phù hợp cho bạn. Khám phá chương trình bootcamp được công nhận trên toàn cầu này và hãy yên tâm rằng việc hoàn thành chương trình này sẽ là bước đi thông minh nhất mà bạn có thể thực hiện để tham gia và phát triển trong nghề phát triển phần mềm

Bạn có câu hỏi nào về hướng dẫn này về thuật toán là gì không? . Các chuyên gia của chúng tôi sẽ trả lời câu hỏi của bạn nhanh nhất có thể

Thông tin về các Tác giả

Soni Upadhyay cùng với Nhóm phân tích nghiên cứu của Simplilearn. Cô ấy tốt nghiệp Khoa học Máy tính và Kỹ thuật. Ngôn ngữ lập trình là lĩnh vực chuyên môn của cô ấy. Cô ấy có kiến ​​thức tuyệt vời về ngôn ngữ lập trình C, C++ và Java

Cấu trúc dữ liệu và thuật toán trong Python là gì?

Python có phải là tốt nhất cho cấu trúc dữ liệu và thuật toán không?

Cái nào tốt hơn cho DSA C++ hoặc Python?

4 cấu trúc dữ liệu tích hợp sẵn trong Python là gì?