NOTASI STANDAR DAN BEBERAPA FUNGSI UMUM

ANALISIS ALGORITMA

2 MARET 2015

OUTLINE Monotonik Floors dan ceilings Aritmetika modular Polinomial Eksponensial Logaritma Faktorial Iterasi fungsional Bilangan Fibonacci

MONOTONIK Fungsi f(n) dikatakan monoton naik jika mn

mengakibatkan f(m) f(n).

Fungsi f(n) dikatakan monoton turun jika mn mengakibatkan f(m)f(n).

Fungsi f(n) disebut fungsi naik sejati jika m < n mengakibatkan f (m) < f (n).

Fungsi f (n) disebut fungsi turun sejati jika m > n mengakibatkan f (m) > f (n).

FLOORS (PEMBULATAN KE BAWAH) DAN CEILINGS (PEMBULATAN KE ATAS)

Untuk bilangan real x: Bilangan bulat terbesar yang lebih kecil atau sama dengan x

dilambangkan dengan x Bilangan bulat terkecil yang lebih besar atau sama dengan x

dilambangkan dengan x. Untuk semua bilangan real x, x-1 < x x x < x+1

Untuk sembarang bilangan bulat n, n/2 + n/2 = n

Untuk sembarang bilangan real n0 dan bilangan bulat a, b>0 n/a/b = n/ab, dan n/a/b = n/ab

a/b (a+(b-1))/b, dan a/b (a- (b-1))/b Fungsi pembulatan ke bawah dan ke atas bersifat monoton

naik.

ARITMETIKA MODULAR Untuk sembarang bilangan bulat a dan sembarang

bilangan bulat positif n, nilai a mod n adalah sisa pembagian a/n:

a mod n = a - a/nn Jika (a mod n) = (b mod n), ditulis ab (mod n) dan

dinyatakan a ekuivalen dengan b, modulo n.

a b (mod n): Jika a dan b memiliki sisa yang sama jika dibagi dengan n Jika dan hanya jika n merupakan pembagi bulat dari b-a

POLINOMIAL Polinomial n berderajat d adalah fungsi: P(n) = adnd +ad-1nd-1 +...+a2n2 +a1n+a0

d adalah bilangan bulat non-negatif ad, ..., a0 adalah konstanta yang disebut koefisien dari

polinomial ad 0

Fungsi positif asimtotik adalah fungsi yang selalu positif untuk n cukup besar.

Suatu polinomial positif asimtotis jika dan hanya jika ad > 0. Untuk sembarang konstanta real a 0 (a0), fungsi na naik

(turun) monoton.

Fungsi f(n) terbatas secara polinomial jika f(n) = O(nk) untuk suatu konstanta k.

EXPONENSIAL Untuk semua bilangan real a>0, m, dan n, terdapat identitas

sbb:

a0=1, a1=a, a1=1/a (am)n = (an)m = amn aman = am+n 00 = 1 (untuk mudahnya)

Untuk semua konstanta bilangan real a dan b sedemikian hingga a > 1,

sehingga dapat disimpulkan bahwa nb = o(an).

Jadi , sembarang fungsi eksponensial dengan basis lebih besar dari 1 naik lebih cepat daripada fungsi polinomial.

LOGARITMA Fungsi logaritma untuk bilangan real x,

e = 2.71828 Untuk semua bilangan real x, kita dapatkan ex 1+x Kesamaan terjadi hanya jika x = 0

Ketika|x|1, kita dapatkan 1 + x ex 1+ x + x2 Ketika x0, kita dapatkan ex = 1+ x +(x2) Untuk semua x,

Notasi-notasi berikut akan digunakan: lg n = log2n (logaritma biner) ln n = logen (logaritma natural) lgk n = (lg n)k (eksponensial) lglg n = lg(lg n) (komposisi)

lgn+k berarti (lgn)+k, bukan lg(n+k). Jika kita mempunyai konstanta b > 1, maka untuk n > 0,

fungsi logbn adalah fungsi naik sejati.

Untuk semua bilangan real a, b, c > 0, dan n, jika basis logaritma tidak 1, kita dapatkan:

ITERASI FUNGSIONAL Misalkan f (n) adalah fungsi pada bilangan real. Maka,

untuk bilangan bulat non-negatif i, secara rekursif kita mendefiniskan

Contoh, jika f(n) = 2n, maka f(i)(n) = 2in

FAKTORIAL Faktorial :

Pendekatan Stirlings

Kompleksitas: n! = o(nn) lg(n!) = (nlgn) n! = (2n)

Untuk semua n 1, kita dapatkan

BILANGAN FIBONACCI Bilangan Fibonacci didefinisikan dengan relasi rekurensi F0 =0, F1 =1, Fi =Fi-1 +Fi-2 for i2.

Bilangan Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Bilangan Fibonacci naik secara eksponensial.