HomeLập trìnhJavaScriptĐộ phức tạp...

Độ phức tạp của các thuật toán và cấu trúc dữ liệu đơn giản trong JS


của Yung L. Leung

GmBtU36F9xkMfZQNnXD8VCoTmXjPDLVydUuS
Ảnh của Karsten Würth trên Bapt

Trong bài viết trước “Một bước tiến tới điện toán như một khoa học: Thuật toán đơn giản & cấu trúc dữ liệu trong JS,” chúng ta đã thảo luận về các thuật toán đơn giản (tìm kiếm tuyến tính & nhị phân; bong bóng, sắp xếp lựa chọn & chèn) & cấu trúc dữ liệu (đối tượng ghép mảng & khóa-giá trị ). Ở đây, tôi tiếp tục với khái niệm về độ phức tạp và ứng dụng của nó đối với các thuật toán & cấu trúc dữ liệu này.

phức tạp

phức tạp là một yếu tố tham gia vào một quá trình phức tạp. Về thuật toán & cấu trúc dữ liệu, đây có thể là thời gian hoặc khoảng trống (có nghĩa là bộ nhớ máy tính) cần thiết để thực hiện một tác vụ cụ thể (tìm kiếm, sắp xếp hoặc truy cập dữ liệu) trên một cấu trúc dữ liệu nhất định. Hiệu quả của việc thực hiện một nhiệm vụ phụ thuộc vào số lượng thao tác cần thiết để hoàn thành một nhiệm vụ.

Đổ rác có thể yêu cầu 3 bước (buộc túi rác, mang ra ngoài & bỏ vào thùng rác). Đổ rác có thể đơn giản, nhưng nếu bạn đang đổ rác sau một tuần dài cải tạo, bạn có thể thấy mình không thể hoàn thành nhiệm vụ do một thiếu không gian trong thùng rác.

Hút bụi phòng có thể yêu cầu thực hiện nhiều bước lặp đi lặp lại (bật, quét liên tục đầu chân không qua sàn và tắt). Căn phòng càng lớn, bạn sẽ càng phải quét đầu chân không trên sàn của nó nhiều lần hơn. Như vậy, các thời gian lâu hơn nó sẽ mất để hút bụi phòng.

L12QMT1j9D8t1gr3hUD5nE72YpEsgo3DPowC

Vì vậy, có một mối quan hệ nhân quả trực tiếp giữa số lượng hoạt động được thực hiện và số lượng phần tử được thực hiện trên đó. Có nhiều rác (phần tử) cần phải lấy ra nhiều lần. Điều này có thể dẫn đến một vấn đề về không gian phức tạp. Có nhiều thước vuông (phần tử) đòi hỏi phải quét đầu hút bụi trên sàn nhiều lần. Điều này có thể dẫn đến một vấn đề về thời gian phức tạp.

Đọc thêm  find() so với filter() trong JavaScript – Sự khác biệt được giải thích bằng các ví dụ

Nếu bạn là đổ rác hoặc hút bụi phòngbạn có thể nói rằng số lượng hoạt động (Ô) tăng chính xác với số phần tử (N). Nếu tôi có 1 túi rác, tôi phải đổ rác 1 lần. Nếu tôi có 2 túi rác, tôi phải thực hiện cùng một nhiệm vụ hai lần, giả sử rằng về mặt thể chất, bạn không thể nhấc nhiều hơn một túi cùng một lúc. Vì vậy, Big-O của những công việc này là O = n hoặc O = function(n) hoặc Trên). Đây là một độ phức tạp tuyến tính (một đường thẳng với tương ứng 1 phép toán: 1 phần tử). Vì vậy, 30 thao tác được thực hiện trên 30 phần tử (đường màu vàng trên biểu đồ).

Điều này tương tự như những gì xảy ra khi xem xét thuật toán & cấu trúc dữ liệu.

tìm kiếm

CMLgOmQiGx-An2R8TeY3yghPSmQzfHc4KCsa
nguồn

Các trường hợp tốt nhất để tìm kiếm một mục trong danh sách có thứ tự, lần lượt, là một hằng số Ô(1), giả sử đó là mục đầu tiên trong danh sách của bạn. Vì vậy, nếu mặt hàng bạn đang tìm kiếm luôn được liệt kê đầu tiên, bất kể kích thước danh sách của bạn là bao nhiêu, thì bạn sẽ tìm thấy mặt hàng của mình ngay lập tức. Độ phức tạp của tìm kiếm của bạn không đổi với kích thước danh sách. Các trung bình đến trường hợp xấu nhất của loại tìm kiếm này là độ phức tạp tuyến tính hoặc Trên). Nói cách khác, đối với n mục, tôi phải tìm n lần trước khi tìm thấy mục của mình, do đó tìm kiếm tuyến tính.

BdVrmbkpWAEROeZzJh-WwglcO3ZvE92aE7Co
nguồn

Đối với tìm kiếm nhị phân, trường hợp tốt nhất là O(1), nghĩa là mục tìm kiếm của bạn nằm ở trung điểm. Các trường hợp xấu nhất & trung bình là log cơ số 2 của n hoặc:

Đọc thêm  Cách viết một lời hứa JavaScript
O4yQ5gMCaNxd9A8fGyTmZRoJlZmUvw2aPxmi

Logarit hoặc nhật ký là một cách biểu thị số mũ cho một cơ số nhất định. Vì vậy, nếu có 16 phần tử (n = 16), thì trong trường hợp xấu hơn, sẽ mất 4 bước để tìm số 15 (số mũ = 4).

DSYpZXtP0NNN0Poj2wNYEE-n6wQhuekHm8KY

Hoặc đơn giản: O(log n)

xWIc5wqomKmecGODTG4drhWSHdirPt9D9lSE

sắp xếp

bong bóng

0aAaHJbR5Nb4u4NCSWXn2pomchbOh9ThVPUm
nguồn

Trong sắp xếp bong bóng, mọi mặt hàng được so sánh với phần còn lại của bộ sưu tập để xác định giá trị cao nhất sẽ nổi lên. Vì lý do này, trên trung bình đến trường hợp xấu nhấtđộ phức tạp của nó là O(n²). Hãy nghĩ rằng một vòng lặp được lồng trong một vòng lặp khác.

02WXe7k1k0y-OFHvIwKyyUh0vNZNs0FUVp-G

Vì vậy, đối với mỗi mục, bạn đang so sánh nó với phần còn lại trong bộ sưu tập của mình. Con số này tương đương với 16 phép so sánh (hoặc thao tác) cho 4 phần tử (4² = 16). Các trường hợp tốt nhất là nếu bộ sưu tập của bạn gần như đã được sắp xếp, ngoại trừ một mục duy nhất. Điều này sẽ dẫn đến một vòng so sánh duy nhất. Nghĩa là, bốn phép so sánh được yêu cầu để tạo ra một thành viên của bộ sưu tập bốn mục, đây là một sự phức tạp của Trên).

tuyển chọn

3HuokiI2FYWnn70N50fhDf-9LrLBLu3Xdcfk
nguồn

không giống sắp xếp bong bóngthay vì tăng giá trị cao nhất, sắp xếp lựa chọn chọn giá trị thấp nhất để hoán đổi nó sang vị trí sớm nhất. Tuy nhiên, vì nó yêu cầu so sánh từng mục với phần còn lại của bộ sưu tập, nên nó cũng có độ phức tạp của O(n²).

Chèn

3tfg-fQ3pfT9czmGkS8p41nLAavr2XlPuxVK
nguồn

không giống như bong bóng & loại lựa chọn, sắp xếp chèn chèn mục vào đúng vị trí của nó. Tuy nhiên, giống như các cách sắp xếp trước, cách sắp xếp này cũng yêu cầu so sánh từng mục với phần còn lại của bộ sưu tập, do đó, nó có một trung bình đến trường hợp xấu nhất sự phức tạp của O(n²). giống như sắp xếp bong bóng, nếu chỉ còn một mục để sắp xếp, nó chỉ yêu cầu một vòng so sánh duy nhất để chèn mục vào đúng vị trí của nó. Đó là, nó có trường hợp tốt nhất sự phức tạp của Trên).

Đọc thêm  Hướng dẫn về mảng đối tượng JavaScript – Cách tạo, cập nhật và lặp qua các đối tượng bằng các phương thức mảng JS

Cấu trúc dữ liệu

Mảng

5UN4-lEEiZ5sR3wLv3S0t5RU0bKU4ixbPTB7

Bởi vì phải mất một bước để truy cập một mục của mảng thông qua chỉ mục của nó hoặc thêm/xóa một mục ở cuối mảng, nên độ phức tạp của truy cập, đẩy hoặc bật ra một giá trị trong một mảng là Ô(1). Nhưng trái lại, tìm kiếm tuyến tính thông qua một mảng thông qua chỉ mục của nó, như đã thấy trước đây, có độ phức tạp là Trên).

Ngoài ra, bởi vì một sự thay đổi hoặc không dịch chuyển của một giá trị đến hoặc từ phía trước của một mảng yêu cầu lập chỉ mục lại mỗi phần tử theo sau nó (nghĩa là loại bỏ một phần tử ở chỉ số 0 yêu cầu ghi nhãn lại phần tử ở chỉ số 1 thành chỉ số 0, v.v.), chúng có độ phức tạp là Trên). Việc dán nhãn lại được thực hiện từ đầu đến cuối mảng.

Khóa – Đối tượng được ghép nối giá trị

uSM26U11UIi7pAVC9TOM0Ku20YXoAE7C2UCD
nguồn

truy cập, chèn hoặc loại bỏ một giá trị bằng cách sử dụng một khóa là tức thời và do đó, chúng có độ phức tạp là Ô(1). Tìm kiếm một mặt hàng cụ thể qua từng “hộp ký gửi” bằng cách sử dụng mọi khóa có sẵn về cơ bản là một tìm kiếm tuyến tính. Và vì vậy, nó có độ phức tạp của Trên).

Phần kết luận

phức tạp không chỉ là một chủ đề để thảo luận về các thuật toán & cấu trúc dữ liệu đã được thiết lập. Nếu được sử dụng một cách khôn ngoan, nó có thể là một công cụ hữu ích để đánh giá hiệu quả của công việc bạn làm và mã bạn tạo để giải quyết vấn đề của mình.

Thẩm quyền giải quyết:

https://www.udemy.com/js-algorithms-and-data-structures-masterclass/



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status