Contoh Java Praktis dari Notasi O Besar

1. Ikhtisar

Dalam tutorial ini, kita akan berbicara tentang apa artinya Big O Notation. Kami akan membahas beberapa contoh untuk menyelidiki pengaruhnya terhadap waktu berjalan kode Anda.

2. Intuisi Notasi O Besar

Kita sering mendengar performa suatu algoritma dijelaskan menggunakan Big O Notation.

Studi tentang kinerja algoritme - atau kompleksitas algoritme - termasuk dalam bidang analisis algoritme. Analisis algoritme menjawab pertanyaan tentang berapa banyak sumber daya, seperti ruang disk atau waktu, yang digunakan algoritme.

Kami akan melihat waktu sebagai sumber daya. Biasanya, semakin sedikit waktu yang dibutuhkan algoritme untuk menyelesaikannya, semakin baik.

3. Algoritma Waktu Konstan - O (1)

Bagaimana ukuran input algoritme ini memengaruhi waktu berjalannya? Kunci untuk memahami Big O adalah memahami tingkat pertumbuhan berbagai hal. Tingkat yang dimaksud di sini adalah waktu yang dibutuhkan per ukuran masukan.

Pertimbangkan potongan kode sederhana ini:

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

Jelas, tidak masalah apa n itu, di atas. Potongan kode ini membutuhkan waktu yang konstan untuk dijalankan. Itu tidak tergantung pada ukuran n.

Demikian pula:

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);

Contoh di atas juga waktu yang konstan. Sekalipun membutuhkan waktu 3 kali lebih lama untuk dijalankan, itu tidak tergantung pada ukuran input, n. Kami menunjukkan algoritma waktu konstan sebagai berikut: O (1) . Perhatikan bahwa O (2) , O (3) atau bahkan O (1000) memiliki arti yang sama.

Kami tidak peduli tentang berapa lama waktu yang dibutuhkan untuk berlari, hanya saja itu membutuhkan waktu yang konstan.

4. Algoritma Waktu Logaritmik - O (log n)

Algoritme waktu konstan (tanpa gejala) adalah yang tercepat. Waktu logaritmik adalah yang tercepat berikutnya. Sayangnya, mereka sedikit lebih sulit untuk dibayangkan.

Salah satu contoh umum dari algoritma waktu logaritmik adalah algoritma pencarian biner. Untuk melihat bagaimana mengimplementasikan pencarian biner di Java, klik di sini.

Yang penting di sini adalah bahwa waktu berjalan tumbuh secara proporsional dengan logaritma input (dalam hal ini, masuk ke basis 2):

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

Jika n adalah 8, outputnya adalah sebagai berikut:

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

Algoritme sederhana kami menjalankan log (8) = 3 kali.

5. Algoritma Waktu Linier - O (n)

Setelah algoritma waktu logaritmik, kita mendapatkan kelas tercepat berikutnya: algoritma waktu linier.

Jika kita mengatakan sesuatu tumbuh secara linier, yang kita maksud adalah tumbuh berbanding lurus dengan ukuran inputnya.

Pikirkan loop for yang sederhana:

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

Berapa kali loop untuk dijalankan? n kali, tentu saja! Kami tidak tahu persis berapa lama ini akan berjalan - dan kami tidak khawatir tentang itu.

Yang kita tahu adalah algoritma sederhana yang disajikan di atas akan tumbuh secara linier dengan ukuran inputnya.

Kami lebih memilih waktu berjalan 0.1n daripada (1000n + 1000) , tetapi keduanya masih merupakan algoritma linier; keduanya tumbuh secara langsung sebanding dengan ukuran input mereka.

Sekali lagi, jika algoritme diubah menjadi berikut:

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); }

The runtime would still be linear in the size of its input, n. We denote linear algorithms as follows: O(n).

As with the constant time algorithms, we don't care about the specifics of the runtime. O(2n+1) is the same as O(n), as Big O Notation concerns itself with growth for input sizes.

6. N Log N Time Algorithms – O(n log n)

n log n is the next class of algorithms. The running time grows in proportion to n log n of the input:

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); } } 

For example, if the n is 8, then this algorithm will run 8 * log(8) = 8 * 3 = 24 times. Whether we have strict inequality or not in the for loop is irrelevant for the sake of a Big O Notation.

7. Polynomial Time Algorithms – O(np)

Next up we've got polynomial time algorithms. These algorithms are even slower than n log n algorithms.

The term polynomial is a general term which contains quadratic (n2), cubic (n3), quartic (n4), etc. functions. What's important to know is that O(n2) is faster than O(n3) which is faster than O(n4), etc.

Let's have a look at a simple example of a quadratic time algorithm:

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); } } 

This algorithm will run 82 = 64 times. Note, if we were to nest another for loop, this would become an O(n3) algorithm.

8. Exponential Time Algorithms – O(kn)

Now we are getting into dangerous territory; these algorithms grow in proportion to some factor exponentiated by the input size.

For example, O(2n) algorithms double with every additional input. So, if n = 2, these algorithms will run four times; if n = 3, they will run eight times (kind of like the opposite of logarithmic time algorithms).

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)
  • Terakhir, Big Θ mendeskripsikan himpunan semua algoritme yang berjalan pada kecepatan tertentu (seperti persamaan)

Definisi yang kami cantumkan di atas tidak akurat secara matematis, tetapi akan membantu pemahaman kami.

Biasanya, Anda akan mendengar hal-hal yang dijelaskan menggunakan O Besar , tetapi tidak ada salahnya mengetahui tentang Besar dan Ω Besar.

11. Kesimpulan

Pada artikel ini, kita membahas notasi Big O, dan bagaimana pemahaman kompleksitas algoritme dapat memengaruhi waktu berjalan kode Anda.

Visualisasi yang bagus dari kelas kompleksitas yang berbeda dapat ditemukan di sini.

Seperti biasa, potongan kode untuk tutorial ini dapat ditemukan di GitHub.