Menganalisis Kompleksitas Kode dengan Python

Kompleksitas suatu algoritma adalah ukuran banyaknya waktu dan/atau ruang yang dibutuhkan oleh sebuah algoritma untuk masukan berukuran tertentu (n). Walaupun kompleksitas algoritma memang bergantung pada faktor-faktor spesifik seperti: arsitektur komputer yaitu platform perangkat keras, representasi Abstract Data Type (ADT), efisiensi kompiler, kompleksitas algoritma yang mendasari, serta ukuran masukan. Namun, faktor yang paling berpengaruh biasanya adalah kompleksitas algoritma yang mendasari dan ukuran masukan.

Dalam blog DataCamp Python Data Structures Tutorial Anda dapat mempelajari gambaran dasar struktur data dan penerapannya dalam Python. Artikel tersebut memperkenalkan struktur data dasar di Python. Di sana, Anda akan mempelajari Abstract Data Type dan Struktur Data, Struktur Data Primitif dan Non-Primitif.

Analisis Asimtotik

Analisis asimtotik mengacu pada penghitungan waktu jalan (running time) dari potongan kode atau operasi dalam satuan matematis dari suatu komputasi. Operasinya dihitung dalam bentuk fungsi seperti f(n). Dalam analisis matematika, analisis asimtotik, atau asimtotik, adalah metode untuk menggambarkan perilaku limit.

Waktu yang dibutuhkan oleh algoritma terbagi menjadi tiga jenis: Kasus terburuk (Worst case) - Waktu maksimum yang diperlukan oleh sebuah algoritma dan ini paling sering digunakan saat menganalisis algoritma. Kasus terbaik (Best case) - Waktu minimum yang diperlukan oleh algoritma atau potongan kode dan biasanya tidak dihitung saat menganalisis algoritma. Kasus rata-rata (Average case) - Waktu rata-rata yang dibutuhkan oleh sebuah algoritma atau potongan kode dan kadang diperhitungkan saat menganalisis algoritma.

Notasi asimtotik

Notasi yang umum digunakan untuk menghitung kompleksitas waktu jalan algoritma adalah sebagai berikut:

• Notasi Big O
• Notasi Big θ
• Notasi Big Ω

Notasi Big Oh, Ο

Big O digunakan untuk mengukur kinerja atau kompleksitas suatu algoritma. Dalam istilah yang lebih matematis, ini adalah batas atas laju pertumbuhan suatu fungsi, atau jika sebuah fungsi g(x) tidak tumbuh lebih cepat daripada fungsi f(x), maka g dikatakan sebagai anggota O(f). Secara umum, ini digunakan untuk menyatakan batas atas dari sebuah algoritma dan memberikan ukuran untuk kompleksitas waktu terburuk atau waktu terlama yang mungkin dibutuhkan algoritma untuk selesai.

Notasi Big Omega, Ω

Notasi Ω(n) adalah cara formal untuk menyatakan batas bawah waktu jalan suatu algoritma. Ini mengukur kompleksitas waktu kasus terbaik atau jumlah waktu terbaik yang mungkin dibutuhkan algoritma untuk selesai.

Notasi Big Theta, θ

Notasi θ(n) adalah cara formal untuk menyatakan sekaligus batas bawah dan batas atas waktu jalan suatu algoritma.

Notasi digunakan untuk menentukan kompleksitas berbagai algoritma

Notasi Big O paling sering digunakan, dan hampir selalu dipakai untuk mencari batas atas suatu algoritma, sedangkan notasi Big θ kadang digunakan untuk mendeteksi kasus rata-rata dan notasi Ω adalah yang paling jarang digunakan di antara ketiganya.

Anda akan melihat contoh penggunaan notasi pada algoritma untuk menentukan kompleksitas algoritma tersebut.

Misalnya untuk quick sort:

Quick sort adalah algoritma Divide and Conquer yang digunakan untuk pengurutan. Ini merupakan metode sistematis untuk menempatkan elemen secara berurutan, misalnya menyusun elemen atau angka dalam array secara menaik atau menurun. Algoritma ini memilih pivot atau indeks yang diambil dari array yang diberikan. Pivot dapat dipilih dengan berbagai cara. Contoh yang diimplementasikan di bawah ini memilih elemen pivot sebagai elemen terakhir.

Inti utama Quick sort adalah partisi. Dari sebuah array, dipilih elemen partisi, lalu elemen partisi (misalnya pit) ditempatkan pada posisi yang benar, kemudian elemen yang lebih besar dari partisi ditempatkan di kanan pit, dan elemen yang lebih kecil ditempatkan di kiri pit.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

Array yang telah diurutkan adalah:
2
4
6
8
10
12
Anda akan mendapatkan keluaran:

Array yang telah diurutkan adalah: 2 4 6 8 10 12

Sekarang saatnya menganalisis kompleksitas waktunya. Pertama-tama,

• Kasus terbaik: Ω(n log(n))
• Kasus rata-rata: Θ(n log(n))
• Kasus terburuk: O(n^2)

Sekarang, mari analisis kode di atas.

Kasus terbaik: Ini adalah kasus ketika elemen partisi memilih elemen tengah sebagai pivot. Karena algoritma akan dipanggil secara rekursif pada paruh pertama dan kedua. Jadi, jumlah langkah total yang diperlukan adalah berapa kali dibutuhkan untuk mencapai dari n ke 1 jika Anda membagi masalah menjadi 2 di setiap langkah. Maka ada n/2/2/2/2/..../2=1 sebanyak k kali. Namun, perhatikan bahwa persamaannya sebenarnya: n / 2^k = 1. Karena 2^logn = n, kita dapatkan k = logn. Jadi jumlah langkah (iterasi) yang dibutuhkan algoritma adalah O(log n), yang membuat algoritma menjadi O(n log n) — karena setiap iterasi adalah O(n).

Kasus rata-rata: Untuk kasus rata-rata kita perlu mempertimbangkan semua permutasi array dan menghitung waktu yang dibutuhkan oleh setiap permutasi. Anda dapat merujuknya lebih lanjut pada Merge sort.

Kasus terburuk: Pada kasus terburuk, jika elemen pertama dipilih sebagai pivot, kompleksitas kasus terburuk terjadi ketika masukan yang akan diurutkan dalam urutan menaik atau menurun. Alasan kasus terburuk adalah setelah pemartisian, ukuran salah satu partisi akan 1 dan ukuran lainnya n-1. Di sini, T(n) adalah fungsinya: Jadi, waktu untuk quick sort pada 'n' elemen T(n) = waktu untuk mempartisi 'n' elemen O(n) + waktu untuk quick sort 'n-1' elemen T(n-1). Jadi, T(n) = T(n-1) + O(n) => T(n) = O(n^2)

Contoh

Kode di bawah ini mungkin tidak terlalu canggih, dan Anda mungkin tidak menyebutnya algoritma, tetapi Anda dapat menganggapnya sebagai algoritma karena kode apa pun yang melakukan sesuatu pada dasarnya adalah algoritma dan merupakan cara untuk menyelesaikan masalah tertentu. Algoritma yang dapat Anda lihat di atas adalah penggunaan for loop yang berisi satu pernyataan print.

print('I love Python');

Hello world!
Kompleksitas waktu algoritma di atas adalah O(1) karena selalu membutuhkan satu langkah. Ini adalah waktu konstan.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Bagaimana Anda akan menggambarkan efisiensi algoritma di atas dalam Notasi Big O?

Untuk menganalisis algoritma di atas, Anda perlu mempertimbangkan atau menilai berapa banyak langkah yang diambil oleh algoritma ini. Pada kasus di atas, ada empat item dalam sebuah list, dan Anda perlu mencetak masing-masing satu kali. Tetapi sekarang pikirkan, bagaimana jika ada lebih dari 4 item dalam list, misalnya 15 item — apakah for loop akan mengambil jumlah langkah yang sama juga untuk 15 item dalam list? Karena for loop ini mengambil sebanyak langkah sebagaimana banyaknya elemen, Anda perlu menyatakan bahwa efisiensi algoritma adalah O(N) alih-alih O(1).

Contoh berikut adalah algoritma sederhana berbasis Python untuk menentukan apakah sebuah bilangan adalah prima:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

Kode di atas menerima sebuah bilangan sebagai argumen dan memulai for loop di mana Anda membagi setiap bilangan dari 2 hingga bilangan tersebut dan melihat apakah ada sisa. Jika tidak ada sisa, Anda tahu bahwa bilangan tersebut bukan prima dan segera mengembalikan False. Jika Anda mencapai hingga bilangan tersebut dan selalu menemukan sisa, maka Anda tahu bahwa bilangan itu prima dan Anda mengembalikan True.

Anda dapat menentukan efisiensi algoritma di atas sebagai O(N). Contoh di atas tidak menerima data dalam bentuk array atau list tetapi angka yang dilewatkan sebagai argumen. Jika Anda melewatkan sebuah angka acak seperti 11, for loop berjalan sekitar sebelas langkah. (Sebetulnya berjalan sembilan langkah, karena mulai dari dua dan berakhir tepat sebelum bilangan tersebut.) Untuk bilangan 101, loop berjalan sekitar 101 langkah. Karena jumlah langkah meningkat seiring dengan angka yang dimasukkan ke fungsi, ini adalah contoh klasik O(N).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Pada kode di atas, kompleksitas algoritma adalah O(N). Karena loop kedua berisi 100 sebagai argumen yang dapat diabaikan karena Anda perlu mengekspresikan kompleksitas dengan mengasumsikan N sangat besar.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

Ada dua loop di mana panjang satu loop adalah m, dan panjang loop lainnya adalah n. Selain itu, Anda perlu mengasumsikan m dan n besar, maka kompleksitas operasinya adalah O(n+m). Karena loop berbeda dan menerima masukan yang berbeda, kompleksitasnya bersifat aditif.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

Terdapat for loop bersarang, dan kembali Anda perlu mengasumsikan n dan m besar, maka kompleksitas operasinya adalah O(n*m). Karena loop serupa dan bersarang, kompleksitasnya bersifat multiplicative.

Selamat!

Anda telah mencapai akhir tutorial ini! Sepanjang jalan, Anda mempelajari notasi asimtotik serta alat dasar yang digunakan oleh programmer dan data scientist. Anda baru saja mempelajari cara yang sederhana dan mudah untuk menganalisis kompleksitas yang ditulis dalam bahasa Inggris sehari-hari tanpa istilah teknis dan ketelitian matematis yang mendalam. Walaupun topik struktur data dan algoritma sering dipelajari hanya jika Anda mahasiswa ilmu komputer atau bidang terkait, memiliki pengetahuan dasar tentang topik ini juga penting, meskipun bukan menjadi ahli. Untuk menyelami lebih dalam perjalanan belajar, Anda dapat merujuk tautan ini. Kursus Algoritma MIT OpenCourseWare

Jika Anda ingin mempelajari lebih lanjut tentang Python, lihat kursus DataCamp berikut: