Download Free PDF
Download Free PDF
THUẬT TOÁN VÀ ĐĐ PHHC TP CA NÓ
THUẬT TOÁN VÀ ĐĐ PHHC TP CA NÓ
THUẬT TOÁN VÀ ĐĐ PHHC TP CA NÓ
THUẬT TOÁN VÀ ĐĐ PHHC TP CA NÓ
Thuật toán và độ phức tạp của nó. Đánh giá thời gian thực hiện
Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.
Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.
"Nếu bạn muốn truyền thông tin dưới dạng các tệp trong khoảng cách 5000 dặm, bạn nên gửi dữ liệu qua Internet". Xuất sắc. Bây giờ chúng ta hãy phân tích nó. Nó có hoàn thành nhiệm vụ của chúng ta không?Vâng, vâng, nó làm. Nhưng chúng ta có thể nói gì về sự phức tạp của nó? Hmm, bây giờ mọi thứ đang trở nên thú vị hơn. Thực tế là thuật toán của chúng tôi phụ thuộc rất nhiều vào dữ liệu đầu vào, cụ thể là kích thước của tệp. Nếu chúng ta có 10 megabyte, thì mọi thứ đều ổn. Nhưng nếu chúng ta cần gửi 500 megabyte thì sao? 20 gigabyte? 500 terabyte? 30 petabyte? Thuật toán của chúng tôi sẽ ngừng hoạt động? Không, tất cả lượng dữ liệu này thực sự có thể được chuyển. Nó sẽ mất nhiều thời gian hơn? Nó sẽ được thôi! Bây giờ chúng ta đã biết một tính năng quan trọng trong thuật toán của mình: lượng dữ liệu cần gửi càng lớn thì thời gian chạy thuật toán càng lâu. Nhưng chúng tôi muốn hiểu chính xác hơn về mối quan hệ này (giữa kích thước dữ liệu đầu vào và thời gian cần thiết để gửi nó). Trong trường hợp của chúng tôi, độ phức tạp của thuật toán là tuyến tính . "Tuyến tính" có nghĩa là khi lượng dữ liệu đầu vào tăng lên, thời gian cần thiết để gửi dữ liệu đó sẽ tăng theo tỷ lệ thuận. Nếu lượng dữ liệu tăng gấp đôi, thì thời gian cần thiết để gửi nó sẽ gấp đôi. Nếu dữ liệu tăng 10 lần thì thời gian truyền sẽ tăng 10 lần. Sử dụng ký hiệu O lớn, độ phức tạp của thuật toán của chúng tôi được biểu thị bằng O(n). Bạn nên ghi nhớ ký hiệu này cho tương lai — nó luôn được sử dụng cho các thuật toán có độ phức tạp tuyến tính. Lưu ý rằng chúng tôi không nói về một số thứ có thể thay đổi ở đây: tốc độ Internet, sức mạnh tính toán của máy tính, v.v. Khi đánh giá mức độ phức tạp của một thuật toán, việc xem xét các yếu tố này đơn giản là không hợp lý — trong mọi trường hợp, chúng nằm ngoài tầm kiểm soát của chúng tôi. Ký hiệu Big O thể hiện độ phức tạp của chính thuật toán chứ không phải "môi trường" mà nó chạy trong đó. Hãy tiếp tục với ví dụ của chúng tôi. Giả sử rằng cuối cùng chúng tôi biết rằng chúng tôi cần gửi các tệp có tổng dung lượng 800 terabyte. Tất nhiên, chúng ta có thể hoàn thành nhiệm vụ của mình bằng cách gửi chúng qua Internet. Chỉ có một vấn đề: ở tốc độ truyền dữ liệu hộ gia đình tiêu chuẩn (100 megabit/giây), sẽ mất khoảng 708 ngày. Gần 2 năm! :O Thuật toán của chúng tôi rõ ràng là không phù hợp ở đây. Chúng ta cần một số giải pháp khác! Thật bất ngờ, gã khổng lồ CNTT Amazon đến giải cứu chúng ta! Dịch vụ Xe trượt tuyết của Amazon cho phép chúng tôi tải một lượng lớn dữ liệu lên bộ lưu trữ di động và sau đó vận chuyển đến địa chỉ mong muốn bằng xe tải!
Độ phức tạp của thuật toán này là gì? Tuyến tính, tức là O(n). Số lượng hành động mà chương trình phải thực hiện phụ thuộc vào số lượng số được truyền cho nó. Nếu trong mảng có 100 số thì sẽ có 100 hành động (câu lệnh để hiển thị chuỗi trên màn hình). Nếu có 10.000 số trong mảng thì phải thực hiện 10.000 thao tác. Thuật toán của chúng tôi có thể được cải thiện theo bất kỳ cách nào không? Không. Dù thế nào đi chăng nữa, chúng ta sẽ phải thực hiện N lượt đi qua mảng và thực hiện N câu lệnh để hiển thị các chuỗi trên bàn điều khiển. Hãy xem xét một ví dụ khác. public static void main(String[] args) { LinkedList<Integer> numbers = new LinkedList<>(); numbers.add(0, 20202); numbers.add(0, 123); numbers.add(0, 8283); }
Chúng tôi có một khoảng trống LinkedListđể chèn một số số. Chúng ta cần đánh giá độ phức tạp của thuật toán khi chèn một số vào LinkedList`ví dụ của chúng ta và mức độ phụ thuộc của nó vào số lượng phần tử trong danh sách. Câu trả lời là O(1), tức là độ phức tạp không đổi . Tại sao? Lưu ý rằng chúng tôi chèn từng số vào đầu danh sách. Ngoài ra, bạn sẽ nhớ lại rằng khi bạn chèn một số vào một `LinkedList, các phần tử không di chuyển đi đâu cả. Các liên kết (hoặc tài liệu tham khảo) được cập nhật (nếu bạn quên cách LinkedList hoạt động, hãy xem một trong những bài học cũ của chúng tôi ). Nếu số đầu tiên trong danh sách của chúng ta là x, và chúng ta chèn số y vào đầu danh sách, thì tất cả những gì chúng ta cần làm là: x.previous = y; y.previous = null; y.next = x;
Khi chúng tôi cập nhật các liên kết, chúng tôi không quan tâm có bao nhiêu số đã có trong`LinkedList` , dù là một hay một tỷ. Độ phức tạp của thuật toán là hằng số, tức là O(1).
độ phức tạp logarit
Không hoảng loạn! :) Nếu từ "logarit" khiến bạn muốn đóng bài học này lại và ngừng đọc, hãy đợi vài phút. Sẽ không có bất kỳ phép toán điên rồ nào ở đây (có rất nhiều cách giải thích tương tự ở nơi khác), và chúng tôi sẽ chọn ra từng ví dụ. Hãy tưởng tượng rằng nhiệm vụ của bạn là tìm một số cụ thể trong một dãy 100 số. Chính xác hơn, bạn cần kiểm tra xem nó có ở đó hay không. Ngay sau khi tìm thấy số cần thiết, quá trình tìm kiếm kết thúc và bạn hiển thị thông tin sau trong bảng điều khiển: "Đã tìm thấy số cần thiết! Chỉ mục của nó trong mảng = ...." Bạn sẽ hoàn thành nhiệm vụ này như thế nào? Ở đây, giải pháp rất rõ ràng: bạn cần lặp lại từng phần tử của mảng, bắt đầu từ phần tử đầu tiên (hoặc từ phần tử cuối cùng) và kiểm tra xem số hiện tại có khớp với số bạn đang tìm hay không. Theo đó, số lượng hành động trực tiếp phụ thuộc vào số lượng phần tử trong mảng. Nếu chúng ta có 100 số, thì chúng ta có khả năng cần phải chuyển đến phần tử tiếp theo 100 lần và thực hiện 100 phép so sánh. Nếu có 1000 số thì có thể có 1000 phép so sánh. Đây rõ ràng là độ phức tạp tuyến tính, tức làO(n) . Và bây giờ chúng ta sẽ thêm một sàng lọc vào ví dụ của mình: mảng nơi bạn cần tìm số được sắp xếp theo thứ tự tăng dần . Điều này có thay đổi bất cứ điều gì liên quan đến nhiệm vụ của chúng tôi không? Chúng tôi vẫn có thể thực hiện tìm kiếm thô bạo cho số mong muốn. Nhưng cách khác, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân nổi tiếng .