Notasi Big O

Notasi big O adalah fungsi yang berkaitan dengan kelajuan proses dari pada kelajuan pertambahan data. Notasi big O merupakan sesuatu nilai dari penyeleasian masalah dengan merujuk proses kerja dari penyelesaian masalah tersebut. Sebuah algoritma tidak saja harus benar, tetapi juga harus efisien. Keefesien algoritma diukur dari beberapa jumlah waktu dan ruang (space) memory yang dibutuhkan untuk menjalankannya. Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses. Dengan menggunakan besaran kompleksitas waktu dan ruang algoritma, dapat menentukan laju peningkatan waktu dan ruang yang diperlukan algoritma dengan meningkatkan ukuran masukan n.

Kompleksitas Waktu
Pengukuran kinerja kualitatif algoritma biasanya dilakukan dengan menyatakan kinerja sebagai salah persamaan sederhana yang menunjukkan hubungan antara masukkan dan kinerja. Cara tradisional untuk menyatakan kinrerja adalah dengan menggunakan notasi Big-O (O), yaitu waktu komputasi algoritma berbanding terhadap suatu fungsi tertentu, yaitu : f(n) = O (g(n)) jika dan hanya jika terdapat konstanta c ? 0 dan konstanta n0 ? 0 sehingga |f(n) ? |g(n)| untuk semua n ? n0, dimana n merupakan karakteristik dari masukkan yang diberikan pada algoritma, yang umumnya menunjukkan jumlah data yang ada. Notasi big_O menghilangkan semua konstanta dan factor kecuali yang dominant.
Kompleksitas waktu dibedakan atas tiga macam :
1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), adalah kebutuhan waktu maksimum.

T(n) = O (log n)

Untuk setiap B, N > 0, logBN = K, if BK = N
Jika (base) B tidak disebut, maka default-nya adalah 2 dalam konteks ilmu computer (binary representation).
Contoh :

Log 32 = 5 (karena 25 = 32)
Log 1024 = 10
Log 1048576 = 20
Log 1 milyard = sekitar 30

2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case), adalah kebutuhan waktu minimum.

T(n) = O (n log n)

Misalkan T(n) adalah waktu untuk menyelesaikan masalah dengan ukuran input n.
Maka T(1) = 1 ( 1 adalah quantum time unit ketika memproses base case; ingat konstanta tidak terlalu penting).
Dua buah pemanggilan pengulangan, masing - masing beukuran n/2. waktu yang dibutuhkan untuk menyelesaikan masing - masing nya adalah T(n/2)

T(1) = 1 = 1*1
T(2) = 2 * T(1) + 2 = 4 = 2 * 2
T(4) = 2 * T(2) + 4 = 12 = 4 * 3
T(8) = 2 * T(4) + 8 = 32 = 8 * 4
T(16) = 2 * T(8) + 16 = 80 = 16 * 5
T(32) = 2 * T(16) + 32 = 192 = 32 * 6
T(64) = 2 * T(32) + 64 = 484 = 64 * 7
T(N) = N(1+log N) = N + N log N = O(N log N)

3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case)
Adalah kebutuhan waktu secara rata-rata. Sehingga total yang dibutuhkan (kompleksitas komputasi) oleh algoritma SEAL adalah O (log n) + O (n log N) = O(n log n + log n).

Kompleksitas Ukuran File
Kompleksitas ukuran file terdiri dari proses encoding dan decoding. Proses encoding kompleksitas ukuran file. Pseudo code proses proses untuk melakukan encoding :

set_low = 0.0
set_high = 1.0
while do
CR = high - low
High = low + CR * High_range (simbol)
Low = low +CR * low_range
Endwhile

Proses Decoding Kompleksitas Ukuran File
Proses decoding digunakan untuk melakukan extract data agar data yang telah di encoding dapat dibaca kembali. Untuk proses pengembalian hasil encoding ke file aslinya, memerlukan pada pesan yang di encoding (ES = hasil low terakhir). Pseudo code decoding adalah sebagai berikut :

set_low = 0.0
set_high = 1.0
while do
CR = high - low
ES = (ES - low_range) / CR
Endwhile