Big-O notation

Notasi Big-O dipakai untuk mendefinisikan kompleksitas dari sebuah algoritma. Notasi nya ialah O(n) dimana n adalah banyak nya input.

Big-O dipakai sebagai upper-bound dari sebuah fungsi polynomial. Fungsi polynomial ini adalah hasil analisis dari kompleksitas waktu yang dijalankan sebuah algoritma.

Katakanlah sebuah algoritma punya kompleksitas 3n2+2n+5 Maka upper-bound terdekat nya adalah n2.

Upper-bound ini untuk memudahkan kita menganalisis kompleksitas karena jika algoritma dijalankan dalam komputer dengan realtime, kompleksitas akan terdefinisikan sesuai upper-bound yang dianalisis.

Beberapa tipe-tipe kompleksitas ada:

Constant Complexity

O(n) = 1

Algoritma yang memiliki upper-bound dari fungsi konstan memiliki waktu yang sama bagi setiap intruksi atau seiring bertambahnya input.

Contoh: Mengakses array

Linear Complexity

O(n) = n

Algoritma berjalan dalam waktu yang bertambah secara linear seiring bertambahnya input.

Contoh: Sebuah single loop yang simpel

Logarithmic Complexity

O(n) = log n

Algoritma yang memiliki kompleksitas logaritmik melimitasi waktu yang berjalan mendekati sebuah konstan seiring bertambahnya input. Algoritma dengan kompleksitas ini sangat bagus untuk input yang besar.

Contoh: Binary tree, Binary search

Quadratic Complexity

O(n) = n^2

Algoritma berjalan 2 kali lebih lama dari input yang bertambah. Algoritma dengan kompleksitas ini sangat bagus untuk ukuran input yang kecil.

Contoh: 2-nested loops, Insertion/Bubble/Selection sort

Website CPC dan lainnya

Berikut adalah website yang cocok untuk melatih skill programming. Skill ini sangat bagus bagi kalian yang menginginkan karir di Software Engineering dan Development.

CodeForces

Website yang dipunyai oleh Rusia ini memiliki kelebihan seperti banyaknya jumlah Contest Virtual dan Training Contest yang terbuka. Kalian bisa mencoba simulasi lomba CPC di wbsite ini.

URI Online Judge

Dimiliki oleh region Brazil, website ini sangat bagus untuk beginner yang baru melirik CPC. Jika kode kalian salah, website ini memberitahukan persentase kesalahannya.

TLX Toki Indonesia

Milik Indonesia, website ini sangat bagus bagi kalian yang ingin ikut perlombaan CPC antar kampus negeri. Banyak arsip soal dari kampus seperti ITB, UI, UGM, BINUS, dkk diambil dari website ini.

HackerRank

Website ini tidak terlalu fokus ke CPC. Namun sangat bagus untuk kalian yang ingin membangun karir developer atau SoftEng. Website ini memberi koneksi ke perusahaan yang membutuhkan tenaga IT. Ada banyak soal Coding Interview di website ini.

StackOverflow

Programmer/coder macam apa yang tak kenal StackOverflow? Website ini membuka komunitas IT untuk bertanya dan diskusi seputar masalah teknis di bidangnya. Walaupun komunitas ini terbuka, website ini memiliki aturan diskusi yang sangat deskriptif. Di sini, kalian bisa mendapat reputasi dari hasil diskusi, vote, pertanyaan, dll. Nilai reputasi itu sangat berguna jika ingin menaruhnya di CV kalian nanti. Recruiter IT biasanya merujuk ke website ini. Karena itu, kalian wajib punya akun di website ini :)

Itu saja hasil share session nya, semoga berjumpa lagi sabtu depan!