Các ví dụ Java thực tế về ký hiệu Big O

1. Khái quát chung

Trong hướng dẫn này, chúng ta sẽ nói về ý nghĩa của Ký hiệu Big O. Chúng tôi sẽ đi qua một vài ví dụ để điều tra ảnh hưởng của nó đến thời gian chạy mã của bạn.

2. Trực giác của ký hiệu Big O

Chúng ta thường nghe thấy hiệu suất của một thuật toán được mô tả bằng cách sử dụng Ký hiệu Big O.

Việc nghiên cứu hiệu suất của các thuật toán - hay độ phức tạp của thuật toán - thuộc lĩnh vực phân tích thuật toán. Phân tích thuật toán trả lời câu hỏi một thuật toán tiêu tốn bao nhiêu tài nguyên, chẳng hạn như không gian đĩa hoặc thời gian.

Chúng tôi sẽ xem xét thời gian như một nguồn lực. Thông thường, thuật toán càng mất ít thời gian để hoàn thành thì càng tốt.

3. Thuật toán thời gian không đổi - O (1)

Kích thước đầu vào này của thuật toán ảnh hưởng như thế nào đến thời gian chạy của nó? Chìa khóa để hiểu Big O là hiểu tốc độ mà mọi thứ có thể phát triển. Tỷ lệ được đề cập ở đây là thời gian thực hiện trên mỗi kích thước đầu vào.

Hãy xem xét đoạn mã đơn giản này:

int n = 1000; System.out.println("Hey - your input is: " + n);

Rõ ràng, không quan trọng n là gì , ở trên. Đoạn mã này cần một khoảng thời gian không đổi để chạy. Nó không phụ thuộc vào kích thước của n.

Tương tự:

int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);

Ví dụ trên cũng là thời gian không đổi. Ngay cả khi thời gian chạy dài gấp 3 lần, nó không phụ thuộc vào kích thước của đầu vào, n. Chúng tôi ký hiệu các thuật toán thời gian không đổi như sau: O (1) . Lưu ý rằng O (2) , O (3) hoặc thậm chí O (1000) sẽ có nghĩa giống nhau.

Chúng tôi không quan tâm đến chính xác thời gian chạy là bao lâu, chỉ rằng nó cần thời gian liên tục.

4. Thuật toán thời gian lôgarit - O (log n)

Các thuật toán thời gian không đổi là (về mặt tiệm cận) là nhanh nhất. Thời gian lôgarit là nhanh nhất tiếp theo. Thật không may, chúng phức tạp hơn một chút để tưởng tượng.

Một ví dụ phổ biến của thuật toán thời gian logarit là thuật toán tìm kiếm nhị phân. Để xem cách triển khai tìm kiếm nhị phân trong Java, hãy nhấp vào đây.

Điều quan trọng ở đây là thời gian chạy tăng theo tỷ lệ với logarit của đầu vào (trong trường hợp này, đăng nhập vào cơ số 2):

for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }

Nếu n là 8, đầu ra sẽ như sau:

Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4

Thuật toán đơn giản của chúng tôi đã chạy log (8) = 3 lần.

5. Thuật toán thời gian tuyến tính - O (n)

Sau các thuật toán thời gian logarit, chúng ta có được loại nhanh nhất tiếp theo: thuật toán thời gian tuyến tính.

Nếu chúng ta nói một thứ gì đó phát triển tuyến tính, chúng ta muốn nói rằng nó phát triển tỷ lệ thuận với quy mô đầu vào của nó.

Hãy nghĩ về một vòng lặp for đơn giản:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }

Vòng lặp for này chạy bao nhiêu lần? n lần, tất nhiên! Chúng tôi không biết chính xác sẽ mất bao lâu để quá trình này chạy - và chúng tôi không lo lắng về điều đó.

Những gì chúng ta biết là thuật toán đơn giản được trình bày ở trên sẽ phát triển tuyến tính với kích thước đầu vào của nó.

Chúng tôi muốn một thời gian chạy của 0.1N hơn (1000n + 1000) , nhưng cả hai vẫn là những thuật toán tuyến tính; cả hai đều tăng trưởng tương ứng trực tiếp với quy mô đầu vào của họ.

Một lần nữa, nếu thuật toán được thay đổi thành như sau:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }

Thời gian chạy sẽ vẫn tuyến tính ở kích thước đầu vào của nó, n . Ta ký hiệu các thuật toán tuyến tính như sau: O (n) .

Như với các thuật toán thời gian không đổi, chúng tôi không quan tâm đến các chi tiết cụ thể của thời gian chạy. O (2n + 1) cũng giống như O (n) , vì Ký hiệu Big O liên quan đến sự phát triển của kích thước đầu vào.

6. Thuật toán N Log N Time - O (n log n)

n log n là lớp thuật toán tiếp theo. Thời gian chạy tăng tỷ lệ với n log n của đầu vào:

for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Ví dụ, nếu n là 8, thì thuật toán này sẽ chạy 8 * log (8) = 8 * 3 = 24 lần. Cho dù chúng ta có bất bình đẳng nghiêm ngặt hay không trong vòng lặp for đều không liên quan vì lợi ích của Kí hiệu Big O.

7. Thuật toán thời gian đa thức - O (np)

Tiếp theo, chúng tôi có các thuật toán thời gian đa thức. Các thuật toán này thậm chí còn chậm hơn các thuật toán n log n .

Thuật ngữ đa thức là một thuật ngữ tổng quát chứa các hàm bậc hai (n2) , bậc ba (n3) , tứ phân (n4) , v.v. Điều quan trọng cần biết là O (n2) nhanh hơn O (n3) nhanh hơn O (n4) , v.v.

Hãy xem một ví dụ đơn giản về thuật toán thời gian bậc hai:

for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Thuật toán này sẽ chạy 82 = 64 lần. Lưu ý, nếu chúng ta lồng một vòng lặp for khác, điều này sẽ trở thành thuật toán O (n3) .

8. Thuật toán thời gian hàm mũ - O ( k n)

Bây giờ chúng ta đang đi vào lãnh thổ nguy hiểm; các thuật toán này phát triển tương ứng với một số hệ số lũy thừa theo kích thước đầu vào.

Ví dụ, các thuật toán O (2n) tăng gấp đôi với mỗi đầu vào bổ sung. Vì vậy, nếu n = 2 , các thuật toán này sẽ chạy bốn lần; nếu n = 3 , chúng sẽ chạy tám lần (giống như ngược lại với thuật toán thời gian lôgarit).

O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.

Let's have a look at a simple example of an O(2n) time algorithm:

for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

This algorithm will run 28 = 256 times.

9. Factorial Time Algorithms – O(n!)

In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.

A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.

An explanation of the solution to the traveling salesman problem is beyond the scope of this article.

Instead, let's look at a simple O(n!) algorithm, as in the previous sections:

for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.

Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).

Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).

To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).

Here, the members of our sets are algorithms themselves:

  • Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
  • Cuối cùng, Big Θ mô tả tập hợp tất cả các thuật toán chạy một tốc độ nhất định (nó giống như sự bình đẳng)

Các định nghĩa mà chúng tôi đưa ra ở trên không chính xác về mặt toán học, nhưng chúng sẽ giúp chúng ta hiểu rõ hơn.

Thông thường, bạn sẽ nghe thấy những thứ được mô tả bằng cách sử dụng Big O , nhưng sẽ không có hại gì khi biết về Big Θ và Big Ω.

11. Kết luận

Trong bài viết này, chúng tôi đã thảo luận về ký hiệu Big O và cách hiểu độ phức tạp của thuật toán có thể ảnh hưởng đến thời gian chạy mã của bạn như thế nào .

Bạn có thể tìm thấy một hình ảnh trực quan tuyệt vời về các lớp phức tạp khác nhau tại đây.

Như thường lệ, các đoạn mã cho hướng dẫn này có thể được tìm thấy trên GitHub.