Kompleksitas Waktu tanpa Cop

Kompleksitas Waktu tanpa Cop

Maksudnya adalah menghiraukan Cop di karenakan hampir setiap komputer memiliki waktu memproses operasi dasar berbeda.

Program CariMinimum

DEKLARASI

N:integer //banyak data masukan

x : integer //data yang dibaca

min: integer //data terkecil

i:integer //pencacah pengulangan

ALGORITMA

Read (N)

Read(x)

min <-- x

for i = 2 to N do

read(x)

if x < min then

min <-- x

endif

endfor

write(min)

C(n)

Paling dalam    : <

WORST CASE Tmax(n)          : N

BEST CASE Tmin(n)   : 1

AVERAGE CASE Tavg(n)      : 1+2+3+…+N/N = 1/2 N(N+1)/N

T(n)≈ N

==================================================

Function Palindrom

Deklarasi

i: integer           //indeks pemindai dari kiri

j: integer           //indeks pemindai dari kanan

pal :Boolean    //true jika palindrom false jika tidak

algoritma

i <--1

j <-- n

pal ßtrue

while (i ≤  j) and (pal) do

            if Huruf[i] <> Huruf [j] then

            pal <-- false

            else

            i <-- i + 1

            j <-- j – 1

            endif

endwhile

return pal

C(n)

Paling banyak  : <--

WORST CASE Tmax(n)          : 3 + n

BEST CASE Tmin(n)               : 6

AVERAGE CASE Tavg(n)       : 1+2+3+…+(3+n)/n

==================================================

Type

    PData=^TData;

    TData=record

                info:integer;

                next:PData;

procedure sisip_belakang(data:integer;var awal,akhir:PData);

Deklarasi :

   baru:PData;

Algoritma :    

     new(baru);

     baru^.info <-- data;

     baru^.next <-- nil;

     if awal=nil then

          awal <-- baru;

          akhir <-- baru;

     else

          akhir^.next <-- baru;

          akhir <-- baru;

     endif

C(n)

Paling dalam    : =

WORST CASE Tmax(n)         : N

BEST CASE Tmin(n)              : 1

AVERAGE CASE Tavg(n)      : 1+2+3+…+N/N = 1/2 N(N+1)/N

T(n)≈ N

==================================================

Type

    PData=^TData;

    TData=record

                info:integer;

                next:PData;

procedure hapus_belakang(var awal,akhir:PData);

Deklarasi :

   bantu:PData;

Algoritma:

     if awal=nil then

        write ('Data kosong, penghapusan tidak dilakukan')

     else if awal=akhir then

          dispose(awal);

          awal <-- nil;

          akhir <-- nil;

     else

          bantu <-- awal;

          while(bantu^.next<>akhir) do

              bantu <-- bantu^.next;

          dispose(akhir);

          akhir <-- bantu;

          akhir^.next <-- nil;

     endwhile;

endif;

C(n)

Paling dalam    : =

WORST CASE Tmax(n)         : N

BEST CASE Tmin(n)              : 1

AVERAGE CASE Tavg(n)      : 1+2+3+…+N/N = 1/2 N(N+1)/N

T(n)≈ N

 ==================================================

Type

    PData=^TData;

    TData=record

                info:integer;

                next:PData;

procedure tampil_Linked_List(awal:PData);

Deklarasi :

   bantu:PData;

Algoritma :

     if awal=nil then

        write('Data Kosong')

     else

          bantu <-- awal;

          while bantu<>nil do

               output(bantu^.info);

               bantu <-- bantu^.next;

          endwhile;

     endif;

C(n)

Paling dalam    : =

WORST CASE Tmax(n)          : 1

BEST CASE Tmin(n)               : 1

AVERAGE CASE Tavg(n)      : 1

Kompleksitas Waktu

Program Akar Persamaan Kuadrat

Deklarasi

a,b,c :real

D  :real

X1,X2 :real

Algoritma :

Input(a,b,c)

D <-- b*b – 4 * a * c

If D < 0 then

Output (Akar akar persamaan kuadrat imaginer)

Else

            If D > o then

            X1 <-- (-b + SQRT(D)) / (2*a)

            X2 <-- (-b - SQRT(D)) / (2*a)

Else { D = 0}

            X1 <-- (-b + SQRT(D)) / (2*a)

            X2 <-- X1

Endif

Output (X1,X2)

Endif

C(n)

Input 1

Output 2

<-- 5

* 6

- 2

< 1

>1

/ 3

+ 2

Misalkan, C_{op :}

C_op Input         : a

C_op Output       : b

C_op  <--            : c

C_op  *               : d

C_op  -                : e

C_op  <               : f

C_op >                : g

C_op  /                : h

C_op  +               : i

 

T(n) = a + 2b + 5c + 6d + 2e + f + g +3h + 2i

------------------------------------------------------------------------------------------

program hitung_diskon_harga

Deklarasi:

harga, diskon, total : real

Algoritma:

input (harga)
if harga > 300000 then
diskon <-- harga * 0.4
total <-- harga - diskon
elseif (harga >= 150000) and (harga<=300000) then
diskon <-- harga * 0.2;
total <-- harga – diskon
else if harga < 150000 then
diskon <-- harga * 0.1
total <-- harga – diskon

endif

output (diskon);
output (total);

C(n)

Input   : 1

Output : 2

<--       : 6

>          : 1

<          : 1

>=        : 1

<=        : 1

-           : 1

*          : 3

And     : 1

Misalkan C_op :

C_op Input         : a

C_op Output      : b

C_op <--             : c

C_op >                : d

C_op <                : e

C_op >=             : f

C_op <=             : g

C_op -                 : h

C_op *                : i

C_op And           : j

T(n) = a + 2b + 6c + c + d + e + f + g + h + 3i + j

------------------------------------------------------------------------------------------

Algoritma Hitung_cashback
Deklarasi
     jumlah, subtotal  : integer
     total : real
Algoritma
     Input (jumlah)
     subtotal ← jumlah * 5000
     If (jumlah > 10)
total ← jumlah - 20000
     else
total ← jumlah – 0
     endif
     output (total)


C(n)

Input = 1
Output = 1
← = 3
* 1
- 2
>1

Misalkan, Cop :

Cop Input         : a
Cop Output       : b
Cop  ← : c
Cop  *               : d
Cop  -                : e
Cop >                : f


T(n) = a + b + 3c + d + 2e + f

------------------------------------------------------------------------------------------

Program Aritmatika_dua_buah_Pecahan

Deklarasi

            Type pecahan : record

                                    <a,b:integer>

P1,P2:Pecahan

P3:Pecahan

ALGORITMA

Input(P1.a , P2.b)

Input(P2.a , P2.b)

\\ hitung P3=P1+P2

P3.a  <-- P1.a * P2.b + P1.b * P2.b

P3.b  <-- P1.b * P2.b

Output(P3.a , P3.b)

\\ hitung P3=P1-P2

P3.a  <-- P1.a * P2.b - P1.b * P2.b

P3.b  <-- P1.b * P2.b

Output(P3.a , P3.b)

\\ hitung P3=P1 * P2

P3.a  <-- P1.a * P2.a

P3.b  <-- P1.b * P2.b

Output(P3.a , P3.b)

\\ hitung P3=P1/P2

P3.a  <-- P1.a * P2.b

P3.b  <-- P1.b * P2.a

Output(P3.a , P3.b)

C(n)

* 10

<-- 8

Input 2

Output 4

-1

+ 1

Misalkan C_{op :}

C_op X               : a

C_op <--             : b

C_op Input         : c

C_op Output      : d

C_op -                 : e

C_op +                : f

T(n)= 10a+8b+2c+4d+e+f

------------------------------------------------------------------------------------------

Procedure max_selection_sort_asc;

Deklarasi

arr_angka : array[1..n] of integer;

data: arr_angka

i,j,posisi_max : integer;

temp : integer;

Algoritma

input(data);

for i = n downto 2 do

posisi_max <-- 1;

for j = 2 to i do

if(data[j] > data[posisi_max]) then

posisi_max <-- j;

endif

endfor

temp <-- data[posisi_max];

data[posisi_max] <-- data[i];

data[i] <-- temp;

endfor

output(data);

C(n)

=          : n + (i*n) atau n + n²

<--       :  n + (i*n) + 3n atau n + n² + 3n

>          : (i*n) atau n²

Input    : 1

Output : 1

Misalkan C_op :

C_op =               : a

C_op <--             : b

C_op >                : c

C_op Input          : d

C_op Output       : e

T(n) = (n + (i*n))a + ((n + (i*n))+ 3n)b + (i*n)c + d + e

------------------------------------------------------------------------------------------