Notasi O Besar dan Analisis Algoritma dengan Contoh Python

Pengantar

Biasanya ada beberapa cara untuk memecahkan masalah menggunakan program komputer. Misalnya, ada beberapa cara untuk mengurutkan item dalam array – Anda dapat menggunakan menggabungkan semacam, semacam gelembung, jenis penyisipan, dan seterusnya. Semua algoritme ini memiliki kelebihan dan kekurangannya masing-masing dan tugas pengembang adalah menimbangnya agar dapat memilih algoritme terbaik untuk digunakan dalam kasus penggunaan apa pun. Dengan kata lain, pertanyaan utamanya adalah algoritma mana yang digunakan untuk memecahkan masalah tertentu ketika ada banyak solusi untuk masalah tersebut.

Analisis algoritma mengacu pada analisis kompleksitas algoritma yang berbeda dan menemukan algoritma yang paling efisien untuk memecahkan masalah yang dihadapi. Notasi Big-O adalah ukuran statistik yang digunakan untuk menggambarkan kompleksitas algoritma.

Dalam panduan ini, pertama-tama kita akan meninjau singkat analisis algoritme dan kemudian melihat lebih dalam pada notasi Big-O. Kita akan melihat bagaimana notasi Big-O dapat digunakan untuk menemukan kompleksitas algoritma dengan bantuan berbagai fungsi Python.

Mengapa Analisis Algoritma Penting?

Untuk memahami mengapa analisis algoritma itu penting, kami akan mengambil bantuan contoh sederhana. Misalkan seorang manajer memberikan tugas kepada dua karyawannya untuk merancang algoritma dengan Python yang menghitung faktorial dari angka yang dimasukkan oleh pengguna. Algoritma yang dikembangkan oleh karyawan pertama terlihat seperti ini:

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

Perhatikan bahwa algoritme hanya mengambil bilangan bulat sebagai argumen. Di dalam fact() fungsi variabel bernama product diinisialisasi ke 1. Sebuah loop dijalankan dari 1 untuk n dan selama setiap iterasi, nilai dalam product dikalikan dengan angka yang diulang oleh loop dan hasilnya disimpan dalam product variabel lagi. Setelah loop dieksekusi, product variabel akan berisi faktorial.

Demikian pula, karyawan kedua juga mengembangkan algoritma yang menghitung faktorial suatu bilangan. Karyawan kedua menggunakan fungsi rekursif untuk menghitung faktorial dari bilangan tersebut n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

Manajer harus memutuskan algoritma mana yang akan digunakan. Untuk melakukannya, mereka memutuskan untuk memilih algoritma mana yang berjalan lebih cepat. Salah satu cara untuk melakukannya adalah dengan mencari waktu yang dibutuhkan untuk mengeksekusi kode pada input yang sama.

Di notebook Jupyter, Anda dapat menggunakan %timeit literal diikuti oleh pemanggilan fungsi untuk menemukan waktu yang dibutuhkan oleh fungsi untuk mengeksekusi:

%timeit fact(50)

Ini akan memberi kita:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Outputnya mengatakan bahwa algoritma mengambil 9 mikrodetik (plus/minus 45 nanodetik) per putaran.

Demikian pula, kita dapat menghitung berapa banyak waktu yang dibutuhkan pendekatan kedua untuk mengeksekusi:

%timeit fact2(50)

Ini akan menghasilkan:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Algoritma kedua yang melibatkan rekursi membutuhkan 15 mikrodetik (plus/minus 427 nanodetik).

Waktu eksekusi menunjukkan bahwa algoritma pertama lebih cepat dibandingkan dengan algoritma kedua yang melibatkan rekursi. Ketika berhadapan dengan input besar, perbedaan kinerja bisa menjadi lebih signifikan.

Namun, waktu eksekusi bukanlah metrik yang baik untuk mengukur kompleksitas suatu algoritma karena tergantung pada perangkat kerasnya. Metrik analisis kompleksitas yang lebih objektif untuk suatu algoritma diperlukan. Di sinilah Notasi O besar datang untuk bermain.

Analisis Algoritma dengan Notasi Big-O

Notasi Big-O menandakan hubungan antara input ke algoritma dan langkah-langkah yang diperlukan untuk mengeksekusi algoritma. Ini dilambangkan dengan "O" besar diikuti dengan tanda kurung buka dan tutup. Di dalam kurung, hubungan antara input dan langkah-langkah yang diambil oleh algoritma disajikan menggunakan "n".

Kuncinya adalah – Big-O tidak tertarik pada tertentu contoh di mana Anda menjalankan algoritme, seperti fact(50), melainkan, seberapa baik itu skala diberikan masukan yang meningkat. Ini adalah metrik yang jauh lebih baik untuk mengevaluasi daripada waktu konkret untuk contoh konkret!

Misalnya, jika ada hubungan linier antara input dan langkah yang diambil oleh algoritma untuk menyelesaikan eksekusinya, notasi Big-O yang digunakan adalah O (n). Demikian pula, notasi Big-O untuk fungsi kuadratik is HAI(n²).

Untuk membangun intuisi:

• O (n): pada n=1, 1 langkah diambil. Pada n=10, 10 langkah diambil.
• HAI(n²): pada n=1, 1 langkah diambil. Pada n=10, 100 langkah diambil.

At n=1, keduanya akan melakukan hal yang sama! Ini adalah alasan lain mengapa mengamati hubungan antara input dan jumlah langkah untuk memproses input itu lebih baik daripada hanya mengevaluasi fungsi dengan beberapa input konkret.

Berikut ini adalah beberapa fungsi Big-O yang paling umum:

Nama	O Besar
konstan	O (c)
Linear	O (n)
Kuadrat	HAI(n²)
Kubik	HAI(n³)
Eksponensial	HAI(2ⁿ)
Logaritma	O (log (n))
Log Linier	HAI(nlog(n))

Anda dapat memvisualisasikan fungsi-fungsi ini dan membandingkannya:

Secara umum – sesuatu yang lebih buruk dari linier dianggap sebagai kompleksitas yang buruk (yaitu tidak efisien) dan harus dihindari jika memungkinkan. Kompleksitas linier tidak apa-apa dan biasanya merupakan kejahatan yang diperlukan. Logaritma itu bagus. Konstan luar biasa!

Untuk mendapatkan gambaran tentang bagaimana Big-O dihitung, mari kita lihat beberapa contoh kompleksitas konstan, linier, dan kuadrat.

Kompleksitas Konstan - HAI(C)

Kompleksitas suatu algoritma dikatakan konstan jika langkah-langkah yang diperlukan untuk menyelesaikan eksekusi suatu algoritma tetap konstan, terlepas dari jumlah inputnya. Kompleksitas konstan dilambangkan dengan O (c) dimana c dapat berupa bilangan konstan apa pun.

Mari kita menulis algoritma sederhana dengan Python yang menemukan kuadrat dari item pertama dalam daftar dan kemudian mencetaknya di layar:

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

Dalam skrip di atas, terlepas dari ukuran input, atau jumlah item dalam daftar input items, algoritma hanya melakukan 2 langkah:

1. Menemukan kuadrat dari elemen pertama
2. Mencetak hasilnya di layar.

Oleh karena itu, kompleksitasnya tetap konstan.

Jika Anda menggambar plot garis dengan ukuran yang bervariasi dari items input pada sumbu X dan jumlah langkah pada sumbu Y, Anda akan mendapatkan garis lurus. Mari buat skrip pendek untuk membantu kita memvisualisasikan ini. Berapa pun jumlah inputnya, jumlah langkah yang dieksekusi tetap sama:

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

Kompleksitas Linier - O (n)

Kompleksitas suatu algoritma dikatakan linier jika langkah-langkah yang diperlukan untuk menyelesaikan eksekusi suatu algoritma bertambah atau berkurang secara linier dengan jumlah input. Kompleksitas linier dilambangkan dengan O (n).

Dalam contoh ini, mari kita tulis program sederhana yang menampilkan semua item dalam daftar ke konsol:

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Kompleksitas dari linear_algo() fungsi linier pada contoh di atas karena jumlah iterasi dari for-loop adalah sama dengan ukuran input items susunan. Misalnya, jika ada 4 item dalam items list, for-loop akan dieksekusi 4 kali.

Mari kita cepat membuat plot untuk algoritma kompleksitas linier dengan jumlah input pada sumbu x dan jumlah langkah pada sumbu y:

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Ini akan menghasilkan:

Hal penting yang perlu diperhatikan adalah bahwa dengan input yang besar, konstanta cenderung kehilangan nilainya. Inilah sebabnya mengapa kami biasanya menghapus konstanta dari notasi Big-O, dan ekspresi seperti O(2n) biasanya disingkat menjadi O(n). Baik O(2n) dan O(n) adalah linier – yang penting adalah hubungan liniernya, bukan nilai konkretnya. Misalnya, mari kita ubah linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Ada dua for-loop yang mengulangi input items daftar. Oleh karena itu kompleksitas algoritma menjadi O (2n), namun dalam kasus item tak terbatas dalam daftar input, dua kali tak terhingga masih sama dengan tak terhingga. Kita dapat mengabaikan konstanta 2 (karena pada akhirnya tidak signifikan) dan kompleksitas algoritma tetap ada O (n).

Mari kita visualisasikan algoritme baru ini dengan memplot input pada sumbu X dan jumlah langkah pada sumbu Y:

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Dalam skrip di atas, Anda dapat dengan jelas melihat bahwa kamu=2n, namun, hasilnya linier dan terlihat seperti ini:

Kompleksitas Kuadrat – HAI(n²)

Kompleksitas suatu algoritma dikatakan kuadrat ketika langkah-langkah yang diperlukan untuk mengeksekusi suatu algoritma adalah fungsi kuadrat dari jumlah item dalam input. Kompleksitas kuadrat dilambangkan sebagai HAI(n²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

Kami memiliki loop luar yang mengulangi semua item dalam daftar input dan kemudian loop dalam bersarang, yang lagi-lagi mengulangi semua item dalam daftar input. Jumlah langkah yang dilakukan adalah n*n, di mana n adalah jumlah item dalam array input.

Grafik berikut memplot jumlah input terhadap langkah-langkah untuk algoritma dengan kompleksitas kuadrat:

Kompleksitas Logaritma – O (logn)

Beberapa algoritma mencapai kompleksitas logaritmik, seperti: Pencarian Biner. Pencarian Biner mencari elemen dalam array, dengan mencentang tengah dari array, dan memangkas setengah di mana elemen tidak. Ia melakukan ini lagi untuk setengah yang tersisa, dan melanjutkan langkah yang sama sampai elemen ditemukan. Dalam setiap langkah, itu bagian jumlah elemen dalam array.

Ini membutuhkan array untuk diurutkan, dan bagi kita untuk membuat asumsi tentang data (seperti itu diurutkan).

Ketika Anda dapat membuat asumsi tentang data yang masuk, Anda dapat mengambil langkah-langkah yang mengurangi kompleksitas suatu algoritma. Kompleksitas logaritmik diinginkan, karena mencapai kinerja yang baik bahkan dengan input berskala tinggi.

Menemukan Kompleksitas Fungsi Kompleks?

Dalam contoh sebelumnya, kami memiliki fungsi input yang cukup sederhana. Padahal, bagaimana kita menghitung Big-O dari fungsi yang memanggil (beberapa) fungsi lain pada input?

Mari kita lihat:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

Dalam skrip di atas beberapa tugas sedang dilakukan, pertama, string dicetak 5 kali di konsol menggunakan print penyataan. Selanjutnya, kami mencetak daftar input dua kali di layar, dan akhirnya, string lain dicetak tiga kali di konsol. Untuk menemukan kompleksitas algoritma seperti itu, kita perlu memecah kode algoritma menjadi bagian-bagian dan mencoba menemukan kompleksitas bagian-bagian individual. Tandai kerumitan setiap bagian.

Di bagian pertama kita memiliki:

for i in range(5):
	print("Python is awesome")

Kompleksitas bagian ini adalah O (5) karena lima langkah konstan sedang dilakukan dalam bagian kode ini terlepas dari inputnya.

Selanjutnya, kita memiliki:

for item in items:
	print(item)

Kita tahu kerumitan dari potongan kode di atas adalah O (n). Demikian pula, kompleksitas potongan kode berikut juga O (n):

for item in items:
	print(item)

Akhirnya, dalam potongan kode berikut, sebuah string dicetak tiga kali, maka kompleksitasnya adalah: O (3):

print("Big O")
print("Big O")
print("Big O")

Untuk menemukan kompleksitas keseluruhan, kita hanya perlu menambahkan kompleksitas individual ini:

O(5) + O(n) + O(n) + O(3)

Menyederhanakan hal di atas kita dapatkan:

O(8) + O(2n) = O(8+2n)

Kami mengatakan sebelumnya bahwa ketika input (yang memiliki panjang n dalam kasus ini) menjadi sangat besar, konstanta menjadi tidak signifikan yaitu dua kali atau setengah dari tak terhingga masih tetap tak terhingga. Oleh karena itu, kita dapat mengabaikan konstanta. Kompleksitas akhir dari algoritma adalah O (n)!

Kompleksitas Kasus Terburuk vs Terbaik

Biasanya, ketika seseorang bertanya kepada Anda tentang kompleksitas suatu algoritme – mereka tertarik pada kompleksitas kasus terburuk (Big-O). Terkadang, mereka mungkin tertarik pada kompleksitas kasus terbaik juga (Big-Omega).

Untuk memahami hubungan antara ini, mari kita lihat potongan kode lain:

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

Dalam skrip di atas, kami memiliki fungsi yang mengambil angka dan daftar angka sebagai input. Ini mengembalikan true jika nomor yang diteruskan ditemukan dalam daftar nomor, jika tidak, ia mengembalikan None. Jika Anda mencari 2 dalam daftar, itu akan ditemukan di perbandingan pertama. Ini adalah kompleksitas kasus terbaik dari algoritma di mana item yang dicari ditemukan dalam indeks pencarian pertama. Kompleksitas kasus terbaik, dalam hal ini adalah O (1). Di sisi lain, jika Anda mencari 10, itu akan ditemukan di indeks pencarian terakhir. Algoritme harus mencari semua item dalam daftar, oleh karena itu kompleksitas kasus terburuk menjadi O (n).

Selain kompleksitas kasus terbaik dan terburuk, Anda juga dapat menghitung kompleksitas rata-rata (Big-Theta) dari suatu algoritme, yang memberi tahu Anda "diberi input acak, berapa kompleksitas waktu yang diharapkan dari algoritme"?

Kompleksitas Ruang

Selain kompleksitas waktu, di mana Anda menghitung jumlah langkah yang diperlukan untuk menyelesaikan eksekusi suatu algoritma, Anda juga dapat menemukan kompleksitas ruang yang mengacu pada jumlah ruang yang Anda butuhkan untuk mengalokasikan dalam memori selama eksekusi program.

Lihat contoh berikut:

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

Grafik return_squares() fungsi menerima daftar bilangan bulat dan mengembalikan daftar dengan kotak yang sesuai. Algoritma harus mengalokasikan memori untuk jumlah item yang sama seperti pada daftar input. Oleh karena itu, kompleksitas ruang dari algoritma menjadi O (n).

Kesimpulan

Notasi Big-O adalah metrik standar yang digunakan untuk mengukur kompleksitas suatu algoritma. Dalam panduan ini, kita mempelajari apa itu notasi Big-O dan bagaimana notasi itu dapat digunakan untuk mengukur kompleksitas berbagai algoritma. Kami juga mempelajari berbagai jenis fungsi Big-O dengan bantuan contoh Python yang berbeda. Akhirnya, kami meninjau secara singkat kompleksitas kasus terburuk dan terbaik bersama dengan kompleksitas ruang.