Mengenal dan Menghitung Time Complexity dan Space Complexity

Mungkin terlihat tidak penting, tetapi sangat penting.

Di matakuliah Desain dan Analisis Algoritma, materi tentang ini seharusnya telah tersampaikan dengan baik kepada mahasiswa, namun bagi sebagian mahasiswa (termasuk saya) mungkin dianggap angin lalu dan terkesan tidak penting. Namun percayalah, konsep ini akan sangat penting jika kita berhadapan dengan suatu optimasi algoritma-algoritma yang digunakan didalam sistem yang berskala production. Tidak usah jauh-jauh ke sistem yang sudah production, di technical interview sewaktu melamar kerja kadang ditanyakan kok 🙃.

Dalam menghitung time complexity dan space complexity (yang biasanya dinotasikan dengan Big-O notation), ada beberapa aturan yang perlu dilakukan disini:

• abaikan konstanta, misalkan O(N + 2), maka dianggap O(N) saja.
• abaikan non dominant terms,misalkan O(N² + N), maka dianggap O(N²) saja.

Baiklah, langsung ke pokok bahasan.

Time complexity

Jadi, ini menyatakan berapa lama suatu algoritma berjalan ketika runtime berdasarkan input yang diberikan. Biasa dinotasikan dengan Big-O notation.

Baiklah, langsung contoh saja.

int add(int a, int b) {
    return a + b;
}

Fungsi diatas memiliki time complexity O(1) dikarenakan ia hanya menjalankan sekali instruksi return, berapapun input yang dimasukkan kedalam fungsi.

Kalau fungsi yang ini bagaimana?

double average(double[] numbers) {
    double sum = 0;
    for(double number: numbers) {
        sum += number;
    }
    return sum / numbers.length;
}

Fungsi diatas memiliki time complexity O(n) dikarenakan ia akan menjalankan looping untuk menjumlahkan bilangan-bilangan yang ada didalam array. Jumlah loopingnya bergantung pada panjang array yang dimasukkan kedalam fungsi.

Jika numbers memiliki panjang array 3 dengan isi [2,3,4] , maka fungsi akan menjumlahkan secara urut 2, 3, dan 4, kemudian mengembalikan rata-ratanya. Sehingga, array yang memiliki panjang 3, fungsi akan melakukan looping sebanyak 3 untuk menjumlahkan bilangan-bilangannya, dan seterusnya.

Bagaimana dengan fungsi yang ini?

int func(int n) {
    int count = 0;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= i ; j++) {
            count++;
        }
    }
    return count;
}

Berapa kali count++ dijalankan dengan nilai n sembarang?

• Ketika i = 1 , maka akan dijalankan 1 kali.
• Ketika i = 2 , maka akan dijalankan 2 kali.
• Ketika i = 3 , maka akan dijalankan 3 kali.
• dan seterusnya…

Sehingga, count++ akan dijalankan sebanyak…

Maka time complexitynya O(n²). Ingat² kembali aturan yang sudah saya jelaskan diawal.

Sekarang, kita coba menghitung time complexity sebuah fungsi yang sedikit banyak codenya.

int someFunction(int[] a, int[] b) {
    int x = 0;
    int y = 1;
    for (int i = 0 ; i < a.length ; i++) {
        x += a[i];
    }
    for (int j = 0 ; j < b.length ; j++) {
        y *= b[j];
    }
    for (int k = 0 ; k < 10 ; k++) {
        x += 1;
        y -= 1;
    }
    return x + y;
}

Anggap saja, panjang array a dinotasikan sebagai N , dan panjang array b dinotasikan sebagai M , maka time complexity diatas bisa dihitung sebagai berikut:

Tetapi tunggu, looping for (int k = 0 ; k < 10 ; k++) kompleksitasnya dianggap O(1) karena ia hanya menjalankan looping 10 kali saja, konstan, karena tidak terpengaruh seberapa besar inputnya.

Sehingga setelah dihitung, time complexitynya adalah O(N + M). Ingat² kembali aturan yang sudah saya jelaskan diawal.

Ah tadi contohnya looping aja, kalau rekursif gimana?

int func(int n) {
    if (n <= 1) {
        return 1;
    }
    return func(n-1) + func(n-1);
}

Nahlo, hitungnya bagaimana?

Misalkan dipanggil dengan func(4) , maka kita bisa gambarkan pohon rekursifnya seperti ini…

sorry for my bad handwriting

Lalu cari polanya…

+------+-----------+-----+
|level | node count| or  |
+------+-----------+-----+
|   0  |   1       | 2^0 |
|   1  |   2       | 2^1 |
|   2  |   4       | 2^2 |
|   3  |   8       | 2^3 |
+------+-----------+-----+

Jadi, fungsi diatas memiliki time complexity sebesar O(2^n).

Space complexity

Jadi ini menyatakan berapa banyak ruang dalam memori yang dibutuhkan suatu algoritma ketika beroperasi.

Misalkan ada sebuah fungsi

int add(int a, int b) {
    return a + b;
}

Fungsi ini membutuhkan 2 unit ruang, yaitu 2 parameternya, dan ketika fungsi ini dijalankan, alokasi ruang memori ini akan tetap, berapapun inputnya, sehingga space complexitynya O(1).

Kalau fungsi yang ini

double average(double[] numbers) {
    double sum = 0;
    for(double number: numbers) {
        sum += number;
    }
    return sum / numbers.length;
}

Fungsi ini akan membutuhkan N unit ruang, yaitu parameter numbers nya, dan 1 unit ruang untuk sum. Space complexitynya O(n), dikarenakan fungsi average akan membutuhkan setidaknya N unit ruang di memori, bergantung panjang arraynya.

Kesimpulan & Penutup

Time complexity menyatakan berapa lama suatu algoritma berjalan ketika runtime berdasarkan input yang diberikan, sedangkan space complexity menyatakan berapa banyak ruang dalam memori yang dibutuhkan suatu algoritma ketika beroperasi.

Konsep ini sudah seharusnya dipahami, khususnya bagi mahasiswa ilmu komputer. Ini akan berguna dan sangat membantu ketika kita akan melakukan suatu optimasi-optimasi algoritma dan struktur data yang kita gunakan.

Semoga bermanfaat 😀