Phân tích độ phức tạp trong trường hợp trung bình năm 2024

"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!

Vì vậy, chúng tôi có một thuật toán mới! "Nếu bạn muốn chuyển thông tin dưới dạng các tập tin qua khoảng cách 5000 dặm và làm như vậy sẽ mất hơn 14 ngày để gửi qua Internet, bạn nên gửi dữ liệu trên một chiếc xe tải của Amazon." Chúng tôi đã chọn 14 ngày tùy ý ở đây. Giả sử đây là khoảng thời gian dài nhất mà chúng ta có thể chờ đợi. Hãy phân tích thuật toán của chúng tôi. Còn tốc độ của nó thì sao? Ngay cả khi chiếc xe tải chỉ di chuyển với tốc độ 50 dặm/giờ, nó sẽ đi được 5000 dặm chỉ trong 100 giờ. Đây là hơn bốn ngày một chút! Điều này tốt hơn nhiều so với tùy chọn gửi dữ liệu qua Internet. Và những gì về sự phức tạp của thuật toán này? Nó cũng tuyến tính, tức là O(n)? Không có nó không phải là. Xét cho cùng, chiếc xe tải không quan tâm đến việc bạn chở nó nặng đến mức nào — nó vẫn sẽ chạy với tốc độ như cũ và đến đúng giờ. Cho dù chúng ta có 800 terabyte hay gấp 10 lần, chiếc xe tải vẫn sẽ đến đích trong vòng 5 ngày. Nói cách khác, thuật toán truyền dữ liệu dựa trên xe tải có độ phức tạp không đổi. Ở đây, "hằng số" có nghĩa là nó không phụ thuộc vào kích thước dữ liệu đầu vào. Đặt ổ đĩa flash 1GB vào xe tải, nó sẽ đến trong vòng 5 ngày. Đặt vào đĩa chứa 800 terabyte dữ liệu, nó sẽ đến trong vòng 5 ngày. Khi sử dụng ký hiệu O lớn, độ phức tạp không đổi được ký hiệu là O(1) . Chúng ta đã trở nên quen thuộc với O(n) và O(1) , vì vậy bây giờ hãy xem thêm các ví dụ khác trong thế giới lập trình :) Giả sử bạn được cung cấp một mảng gồm 100 số và nhiệm vụ là hiển thị từng số đó trên Bàn điều khiển. Bạn viết một `for`vòng lặp thông thường thực hiện nhiệm vụ này

  
int[] numbers = new int[100];  
// ...fill the array with numbers
for (int i: numbers) {  
   System.out.println(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 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 .

Ở hàng trên cùng của hình ảnh, chúng ta thấy một mảng được sắp xếp. Chúng ta cần tìm số 23 trong đó. Thay vì lặp lại các số, chúng ta chỉ cần chia mảng thành 2 phần và kiểm tra số ở giữa trong mảng. Tìm số nằm trong ô 4 và kiểm tra nó (hàng thứ hai trong hình). Con số này là 16 và chúng tôi đang tìm kiếm 23. Con số hiện tại ít hơn số mà chúng tôi đang tìm kiếm. Điều đó nghĩa là gì? Nó có nghĩa làtất cả các số trước đó (những số nằm trước số 16) không cần phải kiểm tra : chúng được đảm bảo nhỏ hơn số chúng tôi đang tìm kiếm, vì mảng của chúng tôi đã được sắp xếp! Chúng tôi tiếp tục tìm kiếm trong số 5 yếu tố còn lại. Ghi chú:chúng tôi chỉ thực hiện một so sánh, nhưng chúng tôi đã loại bỏ một nửa số tùy chọn có thể. Chúng ta chỉ còn lại 5 yếu tố. Chúng tôi sẽ lặp lại bước trước đó bằng cách một lần nữa chia mảng con còn lại thành một nửa và một lần nữa lấy phần tử ở giữa (hàng thứ 3 trong hình ảnh). Con số này là 56, và nó lớn hơn số chúng ta đang tìm. Điều đó nghĩa là gì? Điều đó có nghĩa là chúng ta đã loại bỏ 3 khả năng khác: chính số 56 cũng như hai số sau nó (vì chúng được đảm bảo lớn hơn 23, vì mảng đã được sắp xếp). Chúng tôi chỉ còn 2 số để kiểm tra (hàng cuối cùng trong hình ảnh) — các số có chỉ số mảng 5 và 6. Chúng tôi kiểm tra số đầu tiên và tìm thấy thứ chúng tôi đang tìm kiếm — số 23! Chỉ số của nó là 5! Hãy xem kết quả của thuật toán của chúng tôi, và sau đó chúng tôi' sẽ phân tích sự phức tạp của nó. Nhân tiện, bây giờ bạn đã hiểu tại sao điều này được gọi là tìm kiếm nhị phân: nó dựa vào việc chia đôi dữ liệu nhiều lần. Kết quả thật ấn tượng! Nếu chúng tôi sử dụng tìm kiếm tuyến tính để tìm số, chúng tôi sẽ cần tới 10 phép so sánh, nhưng với tìm kiếm nhị phân, chúng tôi đã hoàn thành nhiệm vụ chỉ với 3! Trong trường hợp xấu nhất, sẽ có 4 phép so sánh (nếu ở bước cuối cùng, số chúng ta muốn là khả năng thứ hai trong số các khả năng còn lại, chứ không phải là khả năng đầu tiên. Vậy còn độ phức tạp của nó thì sao? Đây là một điểm rất thú vị :) Thuật toán tìm kiếm nhị phân ít phụ thuộc vào số phần tử trong mảng hơn nhiều so với thuật toán tìm kiếm tuyến tính (nghĩa là phép lặp đơn giản).