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

Xin chào! Bài giảng hôm nay sẽ khác một chút so với những bài còn lại. Nó sẽ khác ở chỗ nó chỉ liên quan gián tiếp đến Java. Tuy nhiên, chủ đề này rất quan trọng đối với mọi lập trình viên. Chúng ta sẽ nói về các thuật toán . Thuật toán là gì? Nói một cách đơn giản, đây là một chuỗi hành động nhất định phải được thực hiện để đạt được kết quả mong muốn . Chúng ta thường sử dụng các thuật toán trong cuộc sống hàng ngày. Ví dụ, mỗi buổi sáng bạn phải đối mặt với một nhiệm vụ: đến trường hoặc nơi làm việc, đồng thời:

• mặc quần áo
• Lau dọn
• Ăn uống đầy đủ

Thuật toán nào sẽ cho phép bạn đạt được kết quả này?

1. Thức dậy với đồng hồ báo thức.
2. Đi tắm, rửa mặt.
3. Chuẩn bị bữa sáng, pha cà phê/trà.
4. Ăn.
5. Nếu bạn chưa ủi quần áo từ tối, hãy ủi chúng.
6. Mặc quần áo.
7. Rời khỏi nhà.

Chuỗi hành động này chắc chắn sẽ cho phép bạn có được kết quả mong muốn. Trong lập trình, mục đích chung của công việc của chúng tôi là liên tục giải quyết vấn đề. Một phần quan trọng của các nhiệm vụ này có thể được thực hiện bằng các thuật toán đã biết. Ví dụ: bạn phải đối mặt với một nhiệm vụ: sắp xếp danh sách 100 tên trong một mảng . Nhiệm vụ này khá đơn giản, nhưng nó có thể được giải quyết theo nhiều cách khác nhau. Đây là một giải pháp: Thuật toán sắp xếp tên theo thứ tự bảng chữ cái:

1. Mua hoặc tải xuống trên Internet “Từ điển tên cá nhân Nga” ấn bản năm 1966.
2. Tìm mọi tên trong danh sách của chúng tôi trong từ điển này.
3. Viết ra một tờ giấy trang nào của từ điển có tên đó.
4. Đặt tên theo thứ tự bằng cách sử dụng các ghi chú trên một tờ giấy.

Liệu chuỗi hành động như vậy có cho phép chúng ta giải quyết vấn đề của mình không? Có, nó sẽ hoàn toàn cho phép điều đó. Liệu giải pháp này có hiệu quả ? Khắc nghiệt. Ở đây chúng ta đến với một đặc tính rất quan trọng khác của thuật toán - tính hiệu quả của chúng . Vấn đề có thể được giải quyết theo những cách khác nhau. Nhưng cả trong lập trình lẫn trong cuộc sống hàng ngày, chúng ta đều chọn phương pháp hiệu quả nhất. Nếu nhiệm vụ của bạn là làm bánh mì kẹp bơ, tất nhiên, bạn có thể bắt đầu bằng việc gieo lúa mì và vắt sữa bò. Nhưng đây sẽ là một giải pháp không hiệu quả - sẽ tốn rất nhiều thời gian và tốn rất nhiều tiền. Để giải quyết vấn đề đơn giản của bạn, bạn chỉ cần mua bánh mì và bơ. Và thuật toán với lúa mì và bò, mặc dù cho phép bạn giải quyết vấn đề nhưng lại quá phức tạp để áp dụng nó vào thực tế. Để đánh giá độ phức tạp của các thuật toán trong lập trình, một ký hiệu đặc biệt đã được tạo ra gọi là Big-O (“big O”) . Big-O cho phép bạn ước tính thời gian thực hiện của một thuật toán phụ thuộc vào dữ liệu được truyền vào nó . Hãy xem ví dụ đơn giản nhất - truyền dữ liệu. Hãy tưởng tượng rằng bạn cần truyền một số thông tin dưới dạng tệp trên một khoảng cách dài (ví dụ: 5000 km). Thuật toán nào sẽ hiệu quả nhất? Nó phụ thuộc vào dữ liệu anh ta phải làm việc. Ví dụ: chúng tôi có một tệp âm thanh có kích thước 10 megabyte. Trong trường hợp này, thuật toán hiệu quả nhất là truyền tệp qua Internet. Nó sẽ chỉ mất một vài phút! Vì vậy, hãy nói lại thuật toán của chúng tôi: “Nếu bạn cần truyền thông tin dưới dạng tệp trong khoảng cách 5000 km, bạn cần sử dụng đường truyền dữ liệu qua Internet.” Tuyệt vời. Bây giờ hãy phân tích nó. Nó có giải quyết được vấn đề của chúng ta không? Nói chung là có, nó hoàn toàn giải quyết được. Nhưng bạn có thể nói gì về sự phức tạp của nó? Hmm, bây giờ mọi chuyện mới thú vị đây. 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 đến, cụ thể là kích thước của tệp. Bây giờ chúng tôi có 10 megabyte và mọi thứ đều ổn. Nếu chúng ta cần chuyển 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 vẫn có thể được chuyển. Sẽ mất nhiều thời gian hơn để hoàn thành? 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: kích thước của dữ liệu được truyền càng lớn thì thuật toán sẽ hoàn thành càng lâu . Nhưng chúng tôi muốn hiểu chính xác hơn mối quan hệ này trông như thế nào (giữa kích thước của dữ liệu và thời gian cần thiết để truyền dữ liệu). Trong trường hợp của chúng tôi, độ phức tạp của thuật toán sẽ là tuyến tính. “Tuyến tính” có nghĩa là khi khối lượng dữ liệu tăng lên, thời gian truyền dữ liệu sẽ tăng theo tỷ lệ tương ứng. Nếu có nhiều dữ liệu hơn gấp 2 lần và sẽ mất gấp 2 lần thời gian để truyền dữ liệu. Nếu có nhiều dữ liệu hơn 10 lần thì thời gian truyền sẽ tăng gấp 10 lần. Sử dụng ký hiệu Big-O, độ phức tạp của thuật toán của chúng tôi được xác định là O(N) . Ký hiệu này được ghi nhớ tốt nhất để tham khảo trong 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. Xin lưu ý: ở đây chúng ta hoàn toàn không nói về những thứ “có thể thay đổi” khác nhau: tốc độ Internet, sức mạnh máy tính của chúng ta, v.v. Khi đánh giá độ phức tạp của một thuật toán, điều này đơn giản là vô nghĩa - dù sao thì chúng ta cũng không có quyền kiểm soát nó. Big-O tự đánh giá thuật toán, bất kể “môi trường” mà nó sẽ phải hoạt động như thế nào. Hãy tiếp tục với ví dụ của chúng tôi. Giả sử cuối cùng kích thước của tệp được chuyển là 800 terabyte. Tất nhiên, nếu chúng ta truyền chúng qua Internet thì vấn đề sẽ được giải quyết. Chỉ có một vấn đề: việc truyền tải qua một liên kết tiêu chuẩn hiện đại (ở tốc độ 100 megabit/giây) mà hầu hết chúng ta sử dụng trong nhà sẽ mất khoảng 708 ngày. Gần 2 năm! :O Vì vậy, 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! Đột nhiên, gã khổng lồ CNTT Amazon đến trợ giúp chúng tôi! Dịch vụ Amazon Snowmobile của nó cho phép bạn tải lượng lớn dữ liệu vào các thiết bị lưu trữ di động và chuyển chúng đến địa chỉ mong muốn bằng xe tải! Vậy là chúng ta có một thuật toán mới! “Nếu bạn cần truyền thông tin dưới dạng tệp trong khoảng cách 5.000 km và quá trình này sẽ mất hơn 14 ngày khi truyền qua Internet, bạn cần sử dụng phương tiện vận tải bằng xe tải của Amazon.” Con số 14 ngày được chọn ngẫu nhiên ở đây: giả sử đây là khoảng thời gian tối đa mà chúng ta có thể chi trả được. Hãy phân tích thuật toán của chúng tôi. Còn tốc độ thì sao? Ngay cả khi chiếc xe tải chỉ di chuyển với tốc độ 50 km/h, nó sẽ đi được quãng đường 5.000 km chỉ trong 100 giờ. Mới đó mà đã hơn bốn ngày rồi! Điều này tốt hơn nhiều so với tùy chọn truyền Internet. Còn độ phức tạp của thuật toán này thì sao? Nó cũng sẽ tuyến tính, O(N)? Không nó sẽ không như vậy. Rốt cuộc, chiếc xe tải không quan tâm bạn chất bao nhiêu - nó vẫn sẽ chạy với tốc độ gần như cũ và đến đúng giờ. Cho dù chúng ta có 800 terabyte hay gấp 10 lần dữ liệu thì xe tải vẫn sẽ đến đó sau 5 ngày. Nói cách khác, thuật toán truyền dữ liệu qua xe tải có độ phức tạp không đổi . “Không đổi” có nghĩa là nó không phụ thuộc vào dữ liệu được truyền vào thuật toán. Đặt một ổ flash 1GB vào xe tải và nó sẽ đến nơi sau 5 ngày. Đặt các đĩa có 800 terabyte dữ liệu vào đó và nó sẽ đến sau 5 ngày. Khi sử dụng Big-O, độ phức tạp không đổi được ký hiệu là O(1) . Vì chúng ta đã làm quen với O(N) vàO(1) , bây giờ chúng ta hãy xem thêm các ví dụ về "lập trình viên" :) Giả sử bạn được cung cấp một mảng gồm 100 số và nhiệm vụ là in từng số đó ra bảng điều khiển. Bạn viết một vòng lặp thông thường forthực hiện nhiệm vụ này

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Độ phức tạp của thuật toán được viết là gì? Tuyến tính, O(N). Số lượng hành động mà chương trình phải thực hiện phụ thuộc vào chính xác có bao nhiêu số được truyền vào nó. Nếu mảng có 100 số thì sẽ có 100 thao tác (xuất ra màn hình), nếu mảng có 10.000 số thì cần 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? KHÔNG. Trong mọi trường hợp, chúng ta sẽ phải thực hiện N đi qua mảng và thực hiện N đầu ra cho bảng điều khiển. Hãy xem 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 ô trống LinkedListđể chèn một số số vào. Chúng ta cần ước tính độ phức tạp của thuật toán chèn một số vào LinkedListví dụ của mình và nó phụ thuộc như thế nào vào số lượng phần tử trong danh sách. Câu trả lời là O(1) - độ phức tạp không đổi . Tại sao? Xin lưu ý: mỗi lần chúng tôi chèn một số vào đầu danh sách. Ngoài ra, như bạn nhớ, khi chèn số vào LinkedListcác phần tử, chúng không bị dịch chuyển đi đâu cả - các liên kết được xác định lại (nếu bạn đột nhiên quên cách LinkedList hoạt động, hãy xem một trong những bài giảng cũ của chúng tôi ). Nếu bây giờ số đầu tiên trong danh sách của chúng ta là số хvà chúng ta chèn số y vào đầu danh sách thì tất cả những gì cần làm là:

x.previous  = y;
y.previous = null;
y.next = x;

Đối với việc định nghĩa lại tham chiếu này, việc hiện tại có bao nhiêu con số không quan trọng đối với chúng tôiLinkedList - ít nhất một, ít nhất một tỷ. Độ phức tạp của thuật toán sẽ không đổi - O(1).

Độ phức tạp logarit

Không hoảng loạn! :) Nếu từ “logarit” khiến bạn muốn kết thúc bài giảng và không đọc tiếp, hãy đợi vài phút. Sẽ không có khó khăn toán học nào ở đây (có rất nhiều cách giải thích như vậy ở những nơi khác), và chúng tôi sẽ phân tích tất cả các ví dụ “trên ngón tay”. Hãy tưởng tượng nhiệm vụ của bạn là tìm một số cụ thể trong một mảng 100 số. Chính xác hơn, hãy kiểm tra xem nó có ở đó không. Ngay khi tìm thấy số được yêu cầu, việc tìm kiếm phải dừng lại và mục "Số được yêu cầu đã được tìm thấy!" sẽ được hiển thị trong bảng điều khiển. Chỉ số của nó trong mảng = ....” Bạn sẽ giải quyết vấn đề như vậ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 cuối cùng) và kiểm tra xem số hiện tại có trùng với số mong muốn hay không. Theo đó, số lượng hành động trực tiếp phụ thuộc vào số phần tử trong mảng. Nếu chúng ta có 100 số thì chúng ta cần đi đến phần tử tiếp theo 100 lần và kiểm tra số đó xem có trùng khớp 100 lần không. Nếu có 1000 số thì sẽ có 1000 bước kiểm tra. Đây rõ ràng là độ phức tạp tuyến tính, O(N) . Bây giờ chúng ta sẽ thêm một điều làm rõ vào ví dụ của mình: mảng mà 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 gì cho nhiệm vụ của chúng ta không? Chúng ta vẫn có thể tìm kiếm con số mong muốn bằng vũ lực. Nhưng thay vào đó 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. Trong đó chúng ta cần tìm số 23. 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ố trung bình trong mảng. Chúng ta tìm số nằm ở ô 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. Điều đó có nghĩa là gì? Rằng tất cả các số trước đó (nằm đến số 16) không cần phải kiểm tra : chúng chắc chắn sẽ nhỏ hơn số chúng ta đang tìm kiếm, bởi vì mảng của chúng ta đã được sắp xếp! Hãy tiếp tục tìm kiếm trong số 5 phần tử còn lại. Chú ý:Chúng tôi mới chỉ thực hiện một lần kiểm tra nhưng chúng tôi đã loại bỏ một nửa số lựa chọn có thể. Chúng ta chỉ còn lại 5 phần tử. Chúng ta sẽ lặp lại bước của mình - một lần nữa chia mảng còn lại cho 2 và lại lấy phần tử ở giữa (dòng 3 trong hình). Con số này là 56, và nó lớn hơn số chúng ta đang tìm. Điều đó có nghĩa là gì? Rằng chúng tôi loại bỏ thêm 3 tùy chọn - chính số 56 và hai số sau nó (chúng chắc chắn 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) - các số có chỉ số mảng là 5 và 6. Chúng tôi kiểm tra số đầu tiên và đây chính là thứ chúng tôi đang tìm kiếm - số 23! Chỉ số của nó = 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ẽ hiểu độ phức tạp của nó. (Nhân tiện, bây giờ bạn đã hiểu tại sao nó được gọi là nhị phân: bản chất của nó là liên tục chia dữ liệu cho 2). Kết quả thật ấn tượng! Nếu chúng ta đang tìm kiếm số mong muốn bằng cách sử dụng tìm kiếm tuyến tính, chúng ta sẽ cần 10 bước kiểm tra, nhưng với tìm kiếm nhị phân, chúng ta đã thực hiện được trong 3 lần! Trong trường hợp xấu nhất, sẽ có 4 người trong số họ, nếu ở bước cuối cùng, con số chúng ta cần hóa ra là số thứ hai chứ không phải số đầu tiên. 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 phụ thuộc ít hơn vào số phần tử trong mảng so với thuật toán tìm kiếm tuyến tính (nghĩa là liệt kê đơn giản). Với 10 phần tử trong mảng, tìm kiếm tuyến tính sẽ cần tối đa 10 lần kiểm tra và tìm kiếm nhị phân sẽ cần tối đa 4 lần kiểm tra. Sự khác biệt là 2,5 lần. Nhưng đối với một mảng gồm 1000 phần tử, tìm kiếm tuyến tính sẽ cần 1000 lần kiểm tra và tìm kiếm nhị phân sẽ chỉ cần 10 ! Sự khác biệt đã là 100 lần rồi! Chú ý:số phần tử trong mảng tăng 100 lần (từ 10 lên 1000) và số lần kiểm tra cần thiết cho tìm kiếm nhị phân chỉ tăng 2,5 lần - từ 4 lên 10. Nếu chúng ta đạt 10.000 phần tử , sự khác biệt thậm chí còn ấn tượng hơn: 10.000 kiểm tra tìm kiếm tuyến tính và tổng cộng 14 kiểm tra nhị phân. Và một lần nữa: số phần tử tăng 1000 lần (từ 10 lên 10000), nhưng số lượng kiểm tra chỉ tăng 3,5 lần (từ 4 lên 14). Độ phức tạp của thuật toán tìm kiếm nhị phân là logarit hoặc theo ký hiệu Big-O là O(log n) . Tại sao nó được gọi như vậy? Logarit là nghịch đảo của lũy thừa. Logarit nhị phân được sử dụng để tính lũy thừa của 2. Ví dụ: chúng ta có 10.000 phần tử mà chúng ta cần phải thực hiện bằng cách sử dụng tìm kiếm nhị phân. Bây giờ bạn có một bức ảnh trước mắt và bạn biết rằng điều này cần tối đa 14 lần kiểm tra. Nhưng điều gì sẽ xảy ra nếu không có hình ảnh nào trước mắt bạn và bạn cần đếm chính xác số lần kiểm tra cần thiết? Chỉ cần trả lời một câu hỏi đơn giản: số 2 nên tăng lên lũy thừa bao nhiêu để kết quả thu được là >= số phần tử đang được kiểm tra? Với 10000 nó sẽ là lũy thừa thứ 14. 2 lũy thừa 13 quá nhỏ (8192) Nhưng 2 lũy thừa 14 = 16384 , con số này thỏa mãn điều kiện của chúng ta (nó >= số phần tử trong mảng). Chúng tôi đã tìm thấy logarit - 14. Đó là số lần kiểm tra chúng tôi cần! :) Các thuật toán và độ phức tạp của chúng là một chủ đề quá rộng để có thể đưa vào một bài giảng. Nhưng biết điều đó là rất quan trọng: trong nhiều cuộc phỏng vấn bạn sẽ gặp phải các vấn đề về thuật toán. Về lý thuyết, tôi có thể giới thiệu cho bạn một số cuốn sách. Một nơi tốt để bắt đầu là “ Thuật toán Grocking ”: mặc dù các ví dụ trong cuốn sách được viết bằng Python nhưng ngôn ngữ và các ví dụ của cuốn sách rất đơn giản. Tùy chọn tốt nhất cho người mới bắt đầu và nó cũng có khối lượng nhỏ. Đọc nghiêm túc hơn: sách của Robert Laforet và Robert Sedgwick . Cả hai đều được viết bằng Java, điều này sẽ giúp bạn học dễ dàng hơn một chút. Rốt cuộc, bạn đã khá quen thuộc với ngôn ngữ này! :) Đối với những học sinh có nền tảng toán tốt, lựa chọn tốt nhất sẽ là cuốn sách của Thomas Corman . Nhưng bạn sẽ không hài lòng chỉ với lý thuyết! “Biết” != “có thể” Bạn có thể thực hành giải các bài toán thuật toán trên HackerRank và Leetcode . Các vấn đề từ đó thường được sử dụng ngay cả trong các cuộc phỏng vấn tại Google và Facebook, vì vậy bạn chắc chắn sẽ không cảm thấy nhàm chán :) Để củng cố tài liệu bài giảng, tôi khuyên bạn nên xem một video hay về Big-O trên YouTube. Hẹn gặp lại các bạn ở những bài giảng tiếp theo! :)