Apa itu Big-O Notation?

Pernahkah Anda bertanya-tanya mengapa program yang Anda tulis membutuhkan waktu lama untuk dijalankan? Mungkin Anda ingin tahu apakah Anda dapat membuat kode Anda lebih efisien. Memahami bagaimana kode berjalan dapat membawa kode Anda ke level berikutnya. Notasi Big-O adalah alat praktis untuk menghitung seberapa efisien kode Anda sebenarnya.

Apa Itu Notasi Big-O?

Notasi Big-O memberi Anda cara untuk menghitung berapa lama waktu yang dibutuhkan untuk menjalankan kode Anda. Anda dapat menentukan waktu secara fisik berapa lama kode Anda berjalan, tetapi dengan metode itu, sulit untuk mengetahui perbedaan waktu yang kecil. Misalnya, waktu yang dibutuhkan antara menjalankan 20 dan 50 baris kode sangat kecil. Namun, dalam program yang besar, ketidakefisienan tersebut dapat bertambah.

Notasi Big-O menghitung berapa banyak langkah yang harus dijalankan oleh algoritme untuk mengukur efisiensinya. Mendekati kode Anda dengan cara ini bisa sangat efektif jika Anda perlu menyesuaikan kode untuk meningkatkan efisiensi. Notasi Big-O akan memungkinkan Anda mengukur algoritme yang berbeda berdasarkan jumlah langkah yang diperlukan untuk menjalankan dan membandingkan efisiensi algoritme secara objektif.

Bagaimana Anda Menghitung Notasi Big-O

Mari pertimbangkan dua fungsi yang menghitung berapa banyak kaus kaki individu di dalam laci. Setiap fungsi mengambil jumlah pasang kaus kaki dan mengembalikan jumlah kaus kaki individu. Kode ini ditulis dengan Python, tetapi itu tidak memengaruhi cara kita menghitung jumlah langkah.

Algoritma 1:

def sockCounter (numberOfPairs):
individualSocks = 0
untuk x dalam rentang (numberOfPairs):
individualSocks = individualSocks + 2
kembali individualSocks

Algoritma 2:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

Ini adalah contoh yang konyol, dan Anda harus dapat dengan mudah mengetahui algoritme mana yang lebih efisien. Tapi untuk latihan, mari kita jalankan masing-masing.

TERKAIT: Apa Fungsi dalam Pemrograman?

Apa Fungsi dalam Pemrograman?

Jika Anda mempelajari cara memprogram kode Anda sendiri, Anda harus memahami apa itu fungsinya.

Algoritma 1 memiliki banyak langkah:

1. Ini memberikan nilai nol ke variabel individualSocks.
2. Ini memberikan nilai satu ke variabel i.
3. Ini membandingkan nilai i dengan numberOfPairs.
4. Ini menambahkan dua ke IndividualSocks.
5. Ini memberikan peningkatan nilai IndividualSocks untuk dirinya sendiri.
6. Itu bertambah satu per satu.
7. Kemudian loop kembali melalui langkah 3 hingga 6 untuk jumlah yang sama seperti (indiviualSocks - 1).

Jumlah langkah yang harus kita selesaikan untuk algoritme satu dapat dinyatakan sebagai:

4n + 2

Ada empat langkah yang harus kita selesaikan sebanyak n kali. Dalam kasus ini, n akan sama dengan nilai numberOfPairs. Ada juga 2 langkah yang diselesaikan satu kali.

Sebagai perbandingan, algoritma 2 hanya memiliki satu langkah. Nilai numberOfPairs dikalikan dengan dua. Kami akan mengungkapkannya sebagai:

1

Jika belum terlihat, sekarang kita dapat dengan mudah melihat bahwa algoritma 2 lebih efisien.

Analisis Big-O

Umumnya, ketika Anda tertarik dengan notasi Big-O dari suatu algoritme, Anda lebih tertarik pada efisiensi keseluruhan dan lebih sedikit tertarik pada analisis butiran halus dari jumlah langkah. Untuk menyederhanakan notasi, kita tinggal menyatakan besarnya efisiensi.

Dalam contoh di atas, algoritma 2 akan diekspresikan sebagai satu:

O (1)

Tetapi algoritma 1 akan disederhanakan sebagai:

Di)

Cuplikan singkat ini memberi tahu kita bagaimana efisiensi algoritme satu dikaitkan dengan nilai n. Semakin besar angkanya, semakin banyak langkah yang harus diselesaikan algoritme.

Kode Linear

Karena kita tidak mengetahui nilai n, akan lebih membantu untuk memikirkan bagaimana nilai n mempengaruhi jumlah kode yang perlu dijalankan. Dalam algoritma 1 kita dapat mengatakan bahwa hubungannya linier. Jika Anda memplot jumlah langkah vs. nilai n Anda mendapatkan garis lurus yang naik.

Kode Kuadrat

Tidak semua hubungan sesederhana contoh linier. Bayangkan Anda memiliki larik 2D dan ingin mencari nilai dalam larik. Anda dapat membuat algoritme seperti ini:

def searchForValue (targetValue, arraySearched):
foundTarget = False
untuk x dalam larik
untuk y dalam x:
jika (y == targetValue):
foundTarget = Benar
return foundTarget

Dalam contoh ini, jumlah langkah bergantung pada jumlah array di arraySearched dan jumlah nilai di setiap array. Jadi, jumlah langkah yang disederhanakan akan menjadi n * n atau n².

Hubungan ini adalah hubungan kuadrat, yang berarti jumlah langkah dalam algoritme kami bertambah secara eksponensial dengan n. Dalam notasi Big-O, Anda akan menuliskannya sebagai:

O (n²)

TERKAIT: Alat Berguna untuk Memeriksa, Membersihkan, dan Mengoptimalkan File CSS

Kode Logaritmik

Meskipun ada banyak hubungan lainnya, hubungan terakhir yang akan kita lihat adalah hubungan logaritmik. Untuk menyegarkan ingatan Anda, log suatu angka adalah nilai eksponen yang diperlukan untuk mencapai angka yang diberi basis. Sebagai contoh:

log 2 (8) = 3

Lognya sama dengan tiga karena jika basis kita adalah 2, kita membutuhkan nilai eksponen 3 untuk mendapatkan angka 8.

Jadi, hubungan fungsi logaritmik adalah kebalikan dari hubungan eksponensial. Saat n meningkat, lebih sedikit langkah baru yang diperlukan untuk menjalankan algoritme.

Sekilas, ini tampak kontra-intuitif. Bagaimana langkah algoritme tumbuh lebih lambat dari n? Contoh yang bagus dari ini adalah pencarian biner. Mari pertimbangkan algoritme untuk mencari angka dalam larik nilai unik.

• Kita akan mulai dengan sebuah array untuk mencari dari yang terkecil hingga terbesar.
• Selanjutnya, kami akan memeriksa nilai di tengah array.
• Jika nomor Anda lebih tinggi, kami akan mengecualikan nomor yang lebih rendah dalam pencarian kami dan jika nomor itu lebih rendah, kami akan mengecualikan nomor yang lebih tinggi.
• Sekarang, kita akan melihat angka tengah dari angka yang tersisa.
• Sekali lagi, kami akan mengecualikan setengah angka berdasarkan apakah nilai target kami lebih tinggi atau lebih rendah dari nilai tengah.
• Kami akan melanjutkan proses ini sampai kami menemukan target kami, atau menentukan bahwa itu tidak ada dalam daftar.

Seperti yang Anda lihat, karena pencarian biner menghilangkan setengah dari nilai yang mungkin setiap lintasan, karena n bertambah besar, efeknya pada berapa kali kita memeriksa array hampir tidak terpengaruh. Untuk mengekspresikannya dalam notasi Big-O, kita akan menulis:

O (log (n))

Pentingnya Notasi Big-O

Negara Big-O memberi Anda cara cepat dan mudah untuk mengomunikasikan seberapa efisien suatu algoritme. Ini membuatnya lebih mudah untuk memutuskan di antara algoritme yang berbeda. Ini bisa sangat membantu jika Anda menggunakan algoritme dari pustaka dan tidak selalu tahu seperti apa kodenya.

Saat pertama kali belajar kode, Anda mulai dengan fungsi linier. Seperti yang Anda lihat dari grafik di atas, itu akan membawa Anda sangat jauh. Tetapi ketika Anda menjadi lebih berpengalaman dan mulai membangun kode yang lebih kompleks, efisiensi mulai menjadi masalah. Pemahaman tentang cara mengukur efisiensi kode Anda akan memberi Anda alat yang Anda butuhkan untuk mulai menyesuaikannya demi efisiensi dan menimbang pro dan kontra dari algoritme.

10 Kesalahan Pemrograman dan Pengkodean yang Paling Umum

Kesalahan pengkodean dapat menyebabkan begitu banyak masalah. Kiat-kiat ini akan membantu Anda menghindari kesalahan pemrograman dan menjaga kode Anda tetap bermakna.

Tentang Penulis