Notasi Asimptotik

Ketika menghitung kompleksitas sebuah algoritma, kita dapat mengabaikan koefisien dari operasi yang tidak terlalu signifikan dan fokus kepada bagian penting dari waktu yang digunakan algoritma yaitu — pertumbuhan waktu — tanpa perlu menambah kerumitan dalam penghitungan kompleksitas algoritma tersebut. Ketika kita mengabaikan koefisien konstanta, kita dapat menggunakan notasi asimptotik. Kali ini akan dibahas tiga jenis bentuk notasi yaitu, big-
$$\Theta$\mathrm{\Theta }$ notation, big-O notation, dan big-$$\Omega$\mathrm{\Omega }$ notation.

Bubble Sort

PROSEDUR bubblesort(input a1,a2,...,an: integer)
KAMUS 
    i, j, x: integer;
ALGORITMA
    for i ← 1 to n-1 do
        for j ← n-1 downto i do
            if a[j-1] > a[j] then
                x ← a[j-1]
                a[j-1] ← a[j]
                a[j] ← x
        endfor
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
←	3 + n2	3n2

Tmin = 3 + n2

Ω(n2)
Tmax = 3n2

O(n2)
Tavg = 3n2

Θ(n2)

Selection Sort

PROSEDUR selectionsort(input a1,a2,...,an: integer)
KAMUS 
    i, j, k, x: integer
ALGORITMA
    for i ← 0 TO n-2 do
        k ← i
        x ← a[i]

        for j ← i+1 to n-1 do
        if a[j] < x then
            k ← j
            x ← a[k] 
        endfor

        a[k] ← a[i]
        a[i] ← x
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
←	2n + n2	2n + 2n2

Tmin = 2n + n2
Ω(n)

Tmax = 2n + 2n2
O(n2)

Tavg = 2n + n2
Θ(n2)

Quick Sort

PROSEDUR quicksort(input a1,a2,...,an: integer, L: integer, R: integer)
KAMUS
    i, j: integer; w, x: Item
ALGORITMA
    i ← L; 
    j ← R;
    x ← a[(L+R) / 2];

    repeat
    while a[i] < x do 
        while x < a[j]
            if i <= j then
                w ← a[i]
                a[i] ← a[j]
                a[j] ← w
                i    ← i+1
                j    ← j-1
            endif

            j ← j + 1
        endwhile

        i ← i + 1
    until i > j

    if L < j then 
        quicksort(a, L, j)
    if i < R then 
        quicksort(a, i, R)

Operasi Dasar	Cn
	Best Case	Worst Case
<=	n log n	n2

Tmin = n log n

Ω(n log n)

Tmax = n2
O(n2)

Tavg = n log n
Θ(n log n)

Binary Search

PROCEDURE BinarySearch(input a1,a2,...,an: integer, x : integer, output idx : integer)

KAMUS
   i, j, mid : integer
   ketemu : boolean

ALGORITMA
   i ← 1
   j ← n
   ketemu ← false

    while (not ketemu) and ( i <= j) do 
        mid ← (i+j) div 2   
        
        if amid = x then 
            ketemu ← true
        else
            if amid < x then
                i←mid + 1
            else
                j←mid - 1;
            endif
        endif
    endwhile 
   
    if ketemu then
        idx←mid
    else
        idx←0 
    endif

Operasi Dasar	Cn
	Best Case	Worst Case
←	1	log n

Tmin = 1
Ω(1)

Tmax = log n
O(log n)

Tavg = log n
Θ(log n)

Menampilkan Bilangan Prima

PROCEDURE tampil_prima(input min, max : integer)

ALGORITMA
    for min to n do
        if (min > 1 and (min <= 3 or (min%2 != 0 and min%3 != 0)))
            print(min)
        endif
    endfor

Operasi Dasar	Cn
	Best Case	Worst Case
print	0	n

Tmin = 0

Ω(0)

Tmax = n
O(n)

Tavg = n
Θ(n)