Menghitung Kompleksitas Cek nilai

Procedure CekNilai

Deklarasi

    Nilai : real

    Ket : string

Algoritma

        Input(Nilai)

        If Nilai>60 then

                    Ket←’Lulus’

        Else

                    Ket←’Tidak Lulus’

         Endif

          Output (Ket)

Endprocedure

Tmin(n)	2
Tmax(n)	n+1
Tavg(n)	2+3+…+(n+1)      n                     ≈ n

Menghitung Kompleksitas status absensi

Procedure status_absensi

Deklarasi

absen , hari, masuk : integer

status : char

keterangan : string

Algoritma

Ket ß ‘ catatan’

input(hari , masuk)

absen ß(masuk/hari)*100

if (absen > 80 or absen = 80) then

output (status ‘A’)

elseif (absen <80) then

output (status ‘C’)

                        endif

output (ket)

write (status)

endprocedure

Tmin(n)	2
Tmax(n)	3
Tavg(n)	2+3 ≈ 5  n   n

Menghitung Kompleksitas mencari nilai terkecil dan status absensi

Procedure mencari_nilai_terkecil (input x1,….,x_y:integer;

                                                            y : integer)

Deklarasi

            Ketemu : boolean

            c,b : integer

Algoritma

            Output(‘banyak angka?’)

            Input (y)

            For b ß1 to y do

                        Input x[b]

            EndFor

            c ß 1

            ketemu ß false

                        While c < n and not(ketemu) do

                                    if x[c] < x[c+1] then

                                                ketemu ß true

                                    else

                                                c ß c+1

                                    endif               

endwhile

            output (x[c])

endprocedure

Tmin(n)	4 + 2n
Tmax(n)	(3+n)+n
Tavg(n)	(4+2n)+...+(3+n+n) ≈ n               n

Menghitung Kompleksitas binary search (2)

Procedure BinarySearch (Input nama_array : tipe_array)
{I.S. : elemen array yang terurut secara ascending sudah terdefinisi}
{F.S. : menampilkan data yg dicari ditemukan atau tidak ditemukan}
Kamus:
Ia, Ib, k : integer
ketemu : boolean
data_cari : tipedata
Algoritma:
input(data_cari) (1)
Ia = 1 (1)
Ib = maks_array (1)
ketemu := false (1)
while (not ketemu) and (Ia ≤ Ib) do (n)
k = (Ia + Ib) div 2 (1)
if (nama_var_array[k] = data_cari) (1)
then
ketemu = true (1)
else (or)
if (nama_var_array[k] < data_cari) (1)
then
Ia = k + 1 (1)
else (or)
Ib = k – 1 (1)
endif
endif
endwhile

Tmin(n)	4
Tmax(n)	n
Tavg(n)	4+...+n(3+) ≈ n      n

Menghitung Kompleksitas binary search

Procedure b_search (Input a₁…a_x: Integer; x: Integer;

                                    Output cari: integer)

Deklarasi

            data: Array[1..20] Of Integer

            i, j, temp, kiri, tengah, kanan, cari, x: Integer

            ketemu: Boolean

Algoritma

            Output(‘Berapa banyak data [maks. 20]? ‘)

            Input(x)

            For i ← 1 To x Do

                        Output(‘Input data ke-‘,data[i])

            EndFor

            For i ← 1 To x Do

                        For j ← x – 1 DownTo i Do

                                    If (data[i] > data[j+1]) Then

                                                temp ← data[i]

                                                data[i] ← data[j+1]

                                                data[j+1] ← temp

                                    EndIf

                        EndFor

            EndFor

Output(‘Data setelah diurutkan:’)

            For i ← 1 To x Do

                        Output(data[i])

            EndFor

            Output(‘Data yang dicari: ‘)

            Input(cari)

            kiri ← data[x]

            kanan ← 1

            ketemu ← False

            While Not(ketemu) Do

                        tengah ← (kiri + kanan) div 2

                        If data[tengah] = cari Then

                                    ketemu ← True

                        ElseIf (cari < data[tengah])

                                    kiri ← tengah – 1

                        Else

                                    kanan ← tengah + 1

                        EndIf

            EndWhile

            If Not(Not(Ketemu)) Then

                        Output(‘Data berada diposisi ke-‘,tengah)

            Else

                        Output(‘Data tidak ditemukan.’)

            EndIf

EndProcedure

·         Banyaknya data adalah a_x, maka x = n.

·         Operasi dasar yang berada dibagian paling dalam adalah operasi “←” (input)

·         Menentukan nilai Tmin(n), Tmax(n) & Tavg(n):

a.       Tmin(n) = 1 + n + [n * (i * 3)]  + n + 4 + [1 * (1 + 1)]

b.       Tmax(n) = 1 + n + [n * (i * 3)]  + n + 4 + [n * (1 + 1) ]

c.       Tavg(n) = 1+n+[n*(i*3)]+n+4+[1*(1+1)]+...+1+n+[n*(i*3)]+n+4+[n*(1+1)]

                                                                           n

Operasi Dasar	Input/“←”
Tmin(n)	1 + n + [n * (i * 3)]  + n + 4 + [1 * (1 + 1)]
Tmax(n)	1 + n + [n * (i * 3)]  + n + 4 + [n * (1 + 1) ]
Tavg(n)	≈ ≈ n

Menghitung Kompleksitas Algoritma Pengurutan Descending

Descending

Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun

kembali humpunan obyek menggunakan aturan tertentu. Mnurut Microsoft Book-shelf,

definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data

ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.

• urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling

kecil.

Contoh : data bilangan 5, 2, 6 dan 4 dapat diurutkan naik menjadi 2, 4, 5, 6 atau diurutkan

turun menjadi 6, 5, 4, 2. Pada data yang bertipe char, nilai data dikatakan lebih kecil atau

lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence)

Keuntungan dari data yang sudah dalam keadaan terurutkan antara lain :

• data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk

dibetulkan, dihapus, disisipi atau digabungkan. Dalam keadaan terurutkan, kita

mudah melakukan pengeekan apakah ada data yang hilang

• melakukan komppilasi program komputer jika tabel-tabel simbol harus dibentuk

• mempercepat proses pencarian data yang harus dilakukan berulang kali.

48

Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data

yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi,

bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi

tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan.

Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara

lain:

• banyak data yang diurutkan

• kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki

• tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media penyimpan

yang lain.

Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan. Metode

pengurutan yang digunakan dapat diklasifikasikan menjadi dua katagori yaitu :

• pengurutan internal, yaitu pengurutan dengan menggunakan larik (array). Larik

tersimpan dalam memori utama komputer

• pengurutan eksternal, yaitu pengurutan dengan menggunakan berkas (sequential

access file). Berkas tersimpan dalam pengingat luar, misalnya cakram atau pita

magnetis.

Untuk menggambarkan pengurutan dengan larik, bisa kita bayangkan semua kartu

terletak di hadapan kita sehingga semua kartu terlihat dengan jelas nomornya. Pada

penyusunan kartu sebagai sebuah berkas, kita bayangkan semua kartu kita tumpuk

sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.

Ini adalah sebuah program urut dengan masukan 4 nama buah, yang kemudian akan di keluarkan secara berurutan berdasarkan abjad. Pengurutan dalam program ini dapat kita lakukan secara descending. Berikut adalah Source Code dari program urut.

Berikut ini adalah contoh source code dari descending

Program Urut;

uses wincrt;

label       

1,2;

var       x : array[0..3] of string;

y : array[0..3] of string;

pilih : char;

i : integer;

procedure Descending;

var      

i,j, tempatnya_min : integer;

min, temp : string;

begin

for j := 0 to 3 do

     begin        

         min := x[j];

                    for i := j to 3 do

begin

    if (x[i] >= min) then

        begin

min := x[i];

tempatnya_min := i;

        end;

end;

        temp := x[j];

        x[j] := x[tempatnya_min];

        x[tempatnya_min] := temp;

end;

clrscr;

gotoXY(5,17); writeln('Hasil data yang telah di urut secara Descending');

for i := 0 to 3 do

begin

     gotoxy(25,19+i); write(x[i]);

end;

       end;

C (n)                C op

                   

input1              a

= 6                   b

+1                    c
output 1           d

T (n) =  a + 6.b + c + d