Giới thiệu Cấu trúc dữ liệu và Giải thuật

Trong DSA Tags #giai-thuat #dsa #cau-truc-du-lieu #algorithms Xuất bản 01/10/2021

Giới thiệu Cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu là cách lập trình để lưu trữ dữ liệu để dữ liệu có thể được sử dụng một cách hiệu quả. Hầu hết mọi ứng dụng doanh nghiệp đều sử dụng nhiều kiểu cấu trúc dữ liệu khác nhau theo cách này hay cách khác. Bài viết này sẽ cung cấp cho bạn sự hiểu biết cơ bản về Cấu trúc dữ liệu và hiểu sự phức tạp của các ứng dụng cấp doanh nghiệp và nhu cầu của các cấu trúc dữ liệu và giải thuật.

Tại sao phải học Cấu trúc dữ liệu và Giải thuật?

Khi các ứng dụng ngày càng phức tạp và nhiều dữ liệu, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt ngay bây giờ:

  • Tìm kiếm dữ liệu - Xem xét kho hàng gồm 1 triệu (106) sản phẩm của một cửa hàng. Nếu ứng dụng tìm kiếm một mục, nó phải tìm kiếm một mục trong 1 triệu (106) mỗi mục sẽ làm chậm quá trình tìm kiếm. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn.
  • Tốc độ bộ xử lý - Tốc độ bộ xử lý mặc dù rất cao nhưng sẽ bị giới hạn nếu dữ liệu tăng lên đến hàng tỷ bản ghi.
  • Nhiều yêu cầu - Vì hàng nghìn người dùng có thể tìm kiếm dữ liệu đồng thời trên một máy chủ web, ngay cả máy chủ nhanh cũng bị lỗi trong khi tìm kiếm dữ liệu.

Cấu trúc dữ liệu ra đời để giải quyết những vấn đề nêu trên. Dữ liệu có thể được tổ chức theo cách mà tất cả các mục có thể không được yêu cầu tìm kiếm và dữ liệu cần thiết có thể được tìm kiếm gần như ngay lập tức.

Các ứng dụng của Cấu trúc dữ liệu và Giải thuật

Các vấn đề tính toán sau đây có thể được giải quyết bằng cách sử dụng Cấu trúc dữ liệu:

  • Dãy số Fibonacci
  • Vấn đề Knapsack
  • Tháp Hà Nội
  • Tất cả các cặp đường đi ngắn nhất của Floyd-Warshall
  • Tìm đường ngắn nhất của Dijkstra
  • Lập kế hoạch dự án

Cấu trúc dữ liệu

Cấu trúc dữ liệu là một cách có hệ thống để tổ chức dữ liệu nhằm sử dụng nó một cách hiệu quả. Các thuật ngữ sau đây là các thuật ngữ nền tảng của cấu trúc dữ liệu.

  • Giao diện - Mỗi cấu trúc dữ liệu có một giao diện. Giao diện đại diện cho tập hợp các hoạt động mà một cấu trúc dữ liệu hỗ trợ. Một giao diện chỉ cung cấp danh sách các hoạt động được hỗ trợ, loại tham số mà chúng có thể chấp nhận và loại trả về của các hoạt động này.
  • Thực hiện - Thực hiện cung cấp biểu diễn bên trong của cấu trúc dữ liệu. Việc triển khai cũng cung cấp định nghĩa của các thuật toán được sử dụng trong các hoạt động của cấu trúc dữ liệu.

Các đặc trưng của Cấu trúc dữ liệu

  • Tính đúng đắn - Việc triển khai cấu trúc dữ liệu nên triển khai giao diện của nó một cách chính xác.
  • Độ phức tạp về thời gian - Khoảng thời gian chạy hoặc thời gian thực hiện các hoạt động của cấu trúc dữ liệu phải càng nhỏ càng tốt.
  • Độ phức tạp về không gian - Việc sử dụng bộ nhớ (RAM) của một hoạt động cấu trúc dữ liệu nên càng ít càng tốt.

Các trường hợp thời gian thực thi

Có ba trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau một cách tương đối.

  • Trường hợp tồi (tệ) nhất - Đây là tình huống mà một hoạt động cấu trúc dữ liệu cụ thể mất nhiều thời gian nhất có thể. Nếu thời gian trong trường hợp xấu nhất của một hoạt động là ƒ(n) thì hoạt động này sẽ không mất nhiều hơn ƒ (n) thời gian trong đó ƒ(n) đại diện cho hàm của n.
  • Trường hợp trung bình - Đây là kịch bản mô tả thời gian thực hiện trung bình của một hoạt động của cấu trúc dữ liệu. Nếu một hoạt động cần ƒ(n) thời gian để thực hiện, thì m hoạt động sẽ mất mƒ (n) thời gian.
  • Trường hợp tốt nhất - Đây là kịch bản mô tả thời gian thực thi ít nhất có thể của một hoạt động của cấu trúc dữ liệu. Nếu một hoạt động mất ƒ(n) thời gian để thực hiện, thì hoạt động thực tế có thể mất thời gian vì số ngẫu nhiên sẽ lớn nhất là ƒ(n).

Các thuật ngữ cơ bản

  • Data - Dữ liệu là các giá trị hoặc tập hợp các giá trị.
  • Data Item - Mục dữ liệu đề cập đến một giá trị đơn vị.
  • Group Items - Mục Nhóm là các mục dữ liệu được chia thành các mục con.
  • Elementary Items - Mục Cơ bản là các mục dữ liệu không thể phân chia.
  • Attribute and Entity - Thuộc tính và thực thể - Thực thể là một thực thể có chứa các thuộc tính hoặc thuộc tính nhất định, có thể được gán giá trị.
  • Entity Set - Tập thực thể - Các thực thể có các thuộc tính giống nhau tạo thành một tập thực thể.
  • Field - Trường là một đơn vị thông tin cơ bản đại diện cho một thuộc tính của một thực thể.
  • Record - Bản ghi là một tập hợp các giá trị trường của một thực thể nhất định.
  • File - Tệp là một tập hợp các bản ghi của các thực thể trong một tập thực thể nhất định.

Giải thuật

Giải thuật là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được kết quả đầu ra mong muốn. Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tức 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ừ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng:

  • Tìm kiếm - Giải thuật tìm kiếm một mục trong cấu trúc dữ liệu.
  • Sắp xếp - Giải thuật sắp xếp các mục theo một thứ tự nhất định.
  • Chèn - Giải thuật chèn mục trong cấu trúc dữ liệu.
  • Cập nhật - Giải thuật cập nhật một mục hiện có trong cấu trúc dữ liệu.
  • Xóa - Giải thuật xóa một mục hiện có khỏi cấu trúc dữ liệu.

Đặc điểm của một Giải thuật

Không phải tất cả các thủ tục/hàm đều có thể được gọi là một giải thuật. Một giải thuật phải có các đặc điểm sau:

  • Rõ ràng - Thuật toán phải rõ ràng và rõ ràng. Mỗi bước (hoặc giai đoạn) của nó, và đầu vào / đầu ra của chúng phải rõ ràng và phải dẫn đến một ý nghĩa duy nhất.
  • Đầu vào - Một thuật toán phải có 0 hoặc nhiều đầu vào được xác định rõ.
  • Đầu ra - Một thuật toán phải có 1 hoặc nhiều đầu ra được xác định rõ ràng và phải phù hợp với đầu ra mong muốn.
  • Tính hữu hạn - Thuật toán phải kết thúc sau một số bước hữu hạn.
  • Tính khả thi - Nên khả thi với các nguồn lực sẵn có.
  • Độc lập - Một thuật toán phải có hướng dẫn từng bước, điều này phải độc lập với bất kỳ mã lập trình nào.

Làm thế nào để viết một giải thuật?

Không có tiêu chuẩn được xác định rõ ràng để viết các giải thuật. Đúng hơn, đó là vấn đề và phụ thuộc vào tài nguyên. Các giải thuật không bao giờ được viết để hỗ trợ một ngôn ngữ/mã lập trình cụ thể.

Như chúng ta biết rằng tất cả các ngôn ngữ lập trình đều có chung các cấu trúc mã cơ bản như vòng lặp (do, for, while), rẽ nhánh (if-else) ... Những cấu trúc chung này có thể được sử dụng để viết một giải thuật.

Thường thì chúng ta nên viết các giải thuật theo cách thức từng bước, nhưng không phải lúc nào cũng vậy. Viết giải thuật là một quá trình và được thực hiện sau khi miền vấn đề được xác định rõ. Đó là chúng ta nên biết miền vấn đề mà chúng ta đang thiết kế một giải pháp.

Ví dụ: Thiết kế giải thuật cộng hai số và hiển thị kết quả

  • Bước 1: START
  • Bước 2: Khai báo 3 biến a, b, c
  • Bước 3: Xác định/Nhập giá trị cho a và b
  • Bước 4: Cộng giá trị của a và b
  • Bước 5: Lưu trữ kết quả (phép cộng bước 4) vào c
  • Bước 6: Hiển thị c
  • Bước 7: STOP

Các giải thuật nói cho Lập trình viên biết làm thế nào để viết mã lệnh cho chương trình. Ngoài ra giải thuật chó thể được viết dưới dạng sau:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Trong thiết kế và phân tích các giải thuật, thông thường phương pháp thứ hai được sử dụng để mô tả một thuật toán. Nó giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không mong muốn và có thể quan sát những thao tác nào đang được sử dụng và quy trình đang diễn ra như thế nào. (Viết số bước, là tùy chọn)

Chúng ta thiết kế một giải thuật để có được một giải pháp của một vấn đề nhất định. Một vấn đề có thể được giải quyết bằng nhiều cách. Do đó, có nhiều giải thuật có thể được giải quyết cho một vấn đề nhất định. Bước tiếp theo là phân tích các giải thuật được đề xuất đó và triển khai giải pháp phù hợp nhất.

Phân tích Giải thuật

Hiệu quả của một thuật toán có thể được phân tích ở hai giai đoạn khác nhau, trước khi thực hiện và sau khi thực hiện. Chúng là những thứ sau -

  • Phân tích tiên nghiệm (A Priori Analysis) - Đây là phân tích lý thuyết của một thuật toán. Hiệu quả của một thuật toán được đo lường bằng cách giả định rằng tất cả các yếu tố khác, ví dụ, tốc độ bộ xử lý, là không đổi và không ảnh hưởng đến việc triển khai.
  • Phân tích thực nghiệm (A Posterior Analysis) - Đây là một phân tích thực nghiệm của một thuật toán. Thuật toán đã chọn được thực hiện bằng ngôn ngữ lập trình. Sau đó được thực hiện trên máy tính đích. Trong phân tích này, các số liệu thống kê thực tế như thời gian chạy và không gian cần thiết sẽ được thu thập.

Chúng ta sẽ chỉ tìm hiểu về phân tích thuật toán tiên nghiệm. Phân tích thuật toán đề cập đến việc thực thi hoặc thời gian chạy của các hoạt động khác nhau có liên quan. Thời gian chạy của một thao tác có thể được định nghĩa là số lượng lệnh máy tính được thực hiện trên mỗi thao tác.

Độ phức tạp của Giải thuật

Giả sử X là một thuật toán và n là kích thước của dữ liệu đầu vào, thời gian và không gian mà thuật toán X sử dụng là hai yếu tố chính, quyết định hiệu quả của X.

  • Yếu tố thời gian - Thời gian được đo bằng cách đếm số lượng các thao tác chính như so sánh trong giải thuật sắp xếp.
  • Yếu tố không gian - Không gian được đo bằng cách đếm không gian bộ nhớ tối đa mà giải thuật yêu cầu.

Độ phức tạp của thuật toán f(n) cung cấp thời gian chạy và / hoặc không gian lưu trữ theo yêu cầu của thuật toán theo n là kích thước của dữ liệu đầu vào.

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

Độ phức tạp không gian của một giải thuật biểu thị lượng không gian bộ nhớ mà giải thuật yêu cầu trong vòng đời của nó. Không gian được yêu cầu bởi một thuật toán bằng tổng của hai thành phần sau:

  • Một phần cố định là không gian cần thiết để lưu trữ dữ liệu và biến nhất định, độc lập với quy mô của vấn đề. Ví dụ, các biến và hằng số đơn giản được sử dụng, kích thước chương trình, ...
  • Một phần biến là một không gian được yêu cầu bởi các biến, kích thước của nó phụ thuộc vào kích thước của bài toán. Ví dụ, cấp phát bộ nhớ động, không gian ngăn xếp đệ quy, ...

Độ phức tạp không gian S(P) của bất kỳ giải thuật P nào là S(P) = C + SP(I), trong đó C là phần cố định và S(I) là phần biến của giải thuật, điều này phụ thuộc vào đặc tính cá thể I. Sau đây là một ví dụ đơn giản cố gắng giải thích các khái niệm

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Ở đây chúng ta có ba biến A, B, C và một hằng số. Do đó S(P) = 1 + 3. Bây giờ, không gian phụ thuộc vào kiểu dữ liệu của các biến và kiểu hằng đã cho và nó sẽ được nhân lên tương ứng.

Độ phức tạp Thời gian

Độ phức tạp thời gian của một giải thuật biểu thị lượng thời gian mà thuật toán yêu cầu để chạy đến khi hoàn thành. Yêu cầu về thời gian có thể được định nghĩa như một hàm số T(n), trong đó T(n) có thể được đo bằng số bước, miễn là mỗi bước tiêu thụ thời gian không đổi.

Ví dụ, phép cộng hai số nguyên n bit thực hiện n bước. Do đó, tổng thời gian tính toán là T(n) = c ∗ n, trong đó c là thời gian thực hiện để cộng hai bit. Ở đây, chúng ta quan sát thấy rằng T(n) tăng tuyến tính khi kích thước đầu vào tăng lên.

Phân tích tiệm cận

Phân tích tiệm cận của một giải thuật đề cập đến việc xác định giới hạn các thao tác toán học chia cho khung của hiệu suất thời gian chạy của nó. Sử dụng phân tích tiệm cận, chúng ta rất có thể kết luận trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất của một thuật toán.

Phân tích tiệm cận bị ràng buộc đầu vào, tức là nếu không có đầu vào cho thuật toán, nó được kết luận là hoạt động trong một thời gian không đổi. Ngoài "đầu vào", tất cả các yếu tố khác được coi là không đổi.

Phân tích tiệm cận đề cập đến việc tính toán thời gian chạy của bất kỳ thao tác nào bằng các đơn vị tính toán. Ví dụ: thời gian chạy của một thao tác được tính là f(n) và có thể đối với hoạt động khác, nó được tính là g(n2). Điều này có nghĩa là thời gian chạy hoạt động đầu tiên sẽ tăng tuyến tính với sự gia tăng của n và thời gian chạy của hoạt động thứ hai sẽ tăng theo cấp số nhân khi n tăng. Tương tự, thời gian chạy của cả hai hoạt động sẽ gần như nhau nếu n nhỏ hơn đáng kể.

Thông thường, thời gian theo yêu cầu của một thuật toán thuộc ba loại:

  • Trường hợp tốt nhất - Thời gian tối thiểu cần thiết để thực hiện chương trình.
  • Trường hợp trung bình - Thời gian trung bình cần thiết để thực hiện chương trình.
  • Trường hợp xấu nhất - Thời gian tối đa cần thiết để thực hiện chương trình.

Ký hiệu tiệm cận

Sau đây là các ký hiệu tiệm cận thường được sử dụng để tính độ phức tạp thời gian chạy của một Giải thuật:

  • Ký hiệu Ο(n) là cách chính thức để biểu thị giới hạn trên của thời gian chạy thuật toán. Nó đo độ phức tạp về thời gian trong trường hợp xấu nhất hoặc khoảng thời gian dài nhất mà một giải thuật có thể mất để hoàn thành.
  • Ký hiệu Ω(n) là cách chính thức để biểu thị giới hạn dưới của thời gian chạy thuật toán. Nó đo lường độ phức tạp thời gian của trường hợp tốt nhất hoặc khoảng thời gian tốt nhất mà một giải thuật có thể có để hoàn thành.
  • Ký hiệu θ(n) là cách chính thức để biểu thị cả giới hạn dưới và giới hạn trên của thời gian chạy giải thuật.

Kí hiệu tiệm cận phổ biến

Sau đây là danh sách một số ký hiệu tiệm cận phổ biến:

  • Hằng số: O(1)
  • Lô-ga-rít: O(log n)
  • Tuyến tính: O(n)
  • n lô-ga-rít n: O(n log n)
  • Bậc hai: O(n2)
  • Bậc ba: O(n3)
  • Đa thức: nO(1)
  • Luỹ thừa: 2O(n)