Analisis Kompleksitas

Penulis : Benedict_p

Dalam dunia pemrograman, sering sekali kita harus memperkirakan kecepatan suatu program atau memori yang diperlukan untuk menjalankan suatu program. Terdapat beberapa cara untuk merepresentasikan perkiraan tersebut. Cara yang paling sering digunakan dalam pemrograman kompetitif adalah dengan menggunakan Big O Notation. Di bab ini kita akan membahas cara melakukan analisis kompleksitas dengan Big O Notation.

Big O Notation

Notasi O besar atau Big O Notation dalam pemrograman kompetitif adalah suatu notasi yang memperkirakan banyaknya operasi yang perlu dilakukan oleh suatu program dari awal sampai akhir bergantung pada inputnya. Banyaknya operasi yang dapat dilakukan oleh komputer pada umumnya dengan bahasa C++ adalah sekitar $10^8\,$operasi tiap detik. Dengan informasi ini dan notasi O besar, kita bisa memperkirakan waktu berjalannya suatu program. Selanjutnya kita akan membahas pembagian Big O Notation.

Gambar: The Coding Bay

$O(1)$

$O(1)$menyatakan bahwa waktu yang diperlukan untuk menjalankan suatu program tidak tergantung pada variabel apapun, disebut juga konstan. Perhatikan contoh di bawah.

#include<iostream>
using namespace std;

int main(){
    int x;
    cin >> x;
    
    // Mencari apakah x adalah bilangan ganjil atau genap.
    
    if(x % 2 == 1){
        cout << "ganjil\n";
    }
    else{
        cout << "genap\n";
    }
    
    return 0;
}

Untuk x bernilai apapun, program tetap hanya menjalankan 2 operasi, yaitu menghitung x % 2 kemudian mengecek apakah nilainya sama dengan 1. Maka program di atas disebut memiliki kompleksitas konstan dan dinotasikan dengan $O(1)$.

$O(N)$

Jika suatu program menjalankan $N$ buah operasi untuk suatu input $N$, program tersebut memiliki kompleksitas $O(N)$. Disebut juga memiliki kompleksitas linear. Perhatikan contoh di bawah.

#include<iostream>
using namespace std;

int main(){
    int N;
    cin >> N;
    
    int sum = 0;
    for(int i = 1; i <= N; ++i){
        sum += i;
    }
    
    return 0;
}

Program melakukan perulangan sebanyak $N$ kali dan menjalankan 1 operasi pada tiap perulangan, sehingga program melakukan $N$ buah operasi. Kita dapat menuliskan kompleksitas program sebagai $O(N)$. Meskipun nantinya program menjalankan lebih dari 1 operasi pada tiap perulangan, kita tetap menuliskan kompleksitas program sebagai $O(N)$. Hal ini dikarenakan Big O Notation, tidak mempertimbangkan faktor konstan. Contoh,

#include<iostream>
using namespace std;

int main(){
    int N;
    cin >> N;
    
    int num = 0, sum = 0, product = 1;
    for(int i = 1; i <= N; ++i){
        num++;
        sum += i;
        product *= i;
    }
    
    return 0;
}

Meskipun program melakukan perulangan terjadi sebanyak $N$ kali dan pada tiap perulangan melakukan 3 operasi, kompleksitas program tetap dituliskan $O(N)$dan bukan $O(3N)$.

$O(N^2)$

Jika suatu program menjalankan sekitar $N^2$ operasi untuk suatu input $N$, maka program memiliki kompleksitas $O(N^2)$. Contoh,

#include<iostream>
using namespace std;

int main(){
    int N; cin >> N;
    
    int sum = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            sum += 2*i - j;
        }
    }
    
    return 0;
}

Program di atas melakukan $N$kali perulangan, kemudian pada tiap perulangan melakukan $N$kali perulangan lagi. Kompleksitas program adalah $O(N \times N)$ atau $O(N^2)$.

#include<iostream>
using namespace std;

int main(){
    int N; cin >> N;
    
    int sum = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= i; ++j){
            sum += 2*i - j;
        }
    }
    
    return 0;
}

Program di atas melakukan $N$ kali perulangan. Pada perulangan pertama terjadi 1 kali perulangan, pada perulangan kedua terjadi 2 kali perulangan, pada perulangan ketiga terjadi 3 kali perulangan, dan selanjutnya. Total operasi yang terjadi adalah $1 + 2 + 3 + … + N = \dfrac{N(N+1)}{2}$. Kita tetap menuliskan kompleksitasnya sebagai $O(N^2)$. Ingat bahwa notasi O besar tidak mempertimbangkan faktor konstan, sehingga kita tidak perlu menuliskan $\dfrac{1}{2}.$ Kemudian jika kita jabarkan $N(N+1) = N^2 + N$. Perhatikan untuk $N$ yang besar, nilai $+\,N$tidak signifikan karena ukuran $N^2$ jauh lebih besar.

$O(NM)$

Program menjalankan sekitar $N \times M$untuk input $N$dan$M$. Contoh,

#include<iostream>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    
    int sum = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= M; ++j){
            sum += i + j;    
        }
    }
}

$O(N!)$

Jika suatu program menjalankan sekitar$N!$ operasi, maka program tersebut memiliki kompleksitas $O(N!)$. Contohnya adalah pada persoalan mencetak semua permutasi untuk bilangan $1$ sampai $N$. (Lihat rekursi)

#include<iostream>
using namespace std;

int N;
int perm[20];
bool used[20];

void generate_permutation(int index){
    if(index >= N){
        // print perm
    }
    else{
        for(int i = 1; i <= N; ++i){
            if(used[i] == false){
                used[i] = true;
                perm[index] = i;
                generate_permutation(index + 1);
                used[i] = false;
            }
        }
    }
}

int main(){
    int N;
    cin >> N;
    
    generate_permutation(0);
    
    return 0;
}

Program di atas mencetak semua permutasi untuk bilangan $1$ sampai $N$. Karena terdapat $N!$ permutasi, maka program di atas memiliki kompleksitas $O(N!)$.