Kompleksitas Waktu Dan Ruang

Program parkir;

Deklarasi :

  jenis                    : string;

  harga_jenis         : integer;

  lama_parkir         : integer;

  total                     : integer;

Algoritma :

  input (jenis)

  input (lama_parkir)

  if (jenis = “Motor”)

    then

      harga_jenis ← 1500

    else

      harga_jenis ← 2500

  endif

  if (lama_parkir <= 5)

    then

      total ← harga_jenis * lama_parkir

    else

      total ← harga_jenis * 5

  endif

  output (total)

end.

Analisis :

Operator = ←

Tmin(n) = 2n

•    Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 2n

• Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• · Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = n² 

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

n² € O (n²)

n² ≤ 2n² ( untuk semua n ≥ 0 )

n² ≤ 2n²

n² ≤ 2n²

C= 2 , Nₒ=0

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

n² € Ω(n⁻¹)

n² ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

n²€ Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

n²≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

n² ≥ n⁻¹

C₂=1,Nₒ=0

Program indeks_massa_tubuh;

Deklarasi :

  berat_badan    : integer;

  tinggi_badan    : integer;

  tinggi_massa   : real;

  imt                   : real;

 Algoritma :

  input (berat_badan)

  input (tinggi_badan)

  tinggi_massa ← tinggi_badan / 100

  imt ← berat_badan / (tinggi_massa * tinggi_massa)

  if (imt <= 14.9)

    then

      output (“SANGAT KURUS”)

    else

      if ((imt >= 15.0) and (imt <= 18.4))

        then

          output (“KURUS”)

        else

          if ((imt >= 18.5) and (imt <= 22.9))

            then

              output (“NORMAL”)

            else

              if ((imt >= 23.0) and (imt <= 27.4))

                then

                  output (“MASSA TUBUH BERLEBIH”)

                else

                  if ((imt >= 27.5) and (imt <= 40.0))

                    then

                      output (“OBESITAS”)

                    else

                      if ((imt > 40.5)

                        then

                          output (“SANGAT OBESITAS”)

                      endif

                    endif

                  endif

               endif

             endif

          endif

end.

Analisis :

Operator = Output

Tmin(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

 

Tmax(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = (1/2n(1+1))/n = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Program menghitung_diskon;

Deklarasi :

  nilai_belanja           : integer;

  input_diskon           : real;

  diskon                      : real;

  harga_belanja        : real;

const

  ketentuan_diskon = 100000;

  skala_persentase = 100;

Algoritma :

  output ('Masukan jumlah nilai belanja anda = ')

  input (nilai_belanja)

    if (nilai_belanja >= ketentuan_diskon) then

      output ('Masukan jumlah diskon dalam skala persentase 1 s/d 100 = ')

      input (input_diskon)

      diskon ←  nilai_belanja * input_diskon / skala_persentase

      harga_belanja ← nilai_belanja - diskon

      output ('Pembeli mendapat diskon sebesar Rp. ', round(diskon))

      output ('Total nilai belanja yang harus dibayar adalah Rp. ', round(harga_belanja))

      if (nilai_belanja < ketentuan_diskon) then

        output ('Pembeli tidak mendapat diskon')

        output ('Total nilai belanja yang harus dibayar adalah Rp. ', nilai_belanja)

      endif

    endif

end.

Analisis :

Operator = ←

Tmin(n) = 2n

•    Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 2n

• Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

2n € O (n²)

2N ≤ 5n² ( untuk semua n ≥ 0)

2N ≤ 5n²

2N ≤ 5n²

C= 5 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

2N € Ω(n⁻¹)

2N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

• · Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

2N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

2N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

2N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) = n² 

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

n² € O (n²)

n² ≤ 2n² ( untuk semua n ≥ 0 )

n² ≤ 2n²

n² ≤ 2n²

C= 2 , Nₒ=0

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

n² € Ω(n⁻¹)

n² ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

n²€ Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

n²≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

n² ≥ n⁻¹

C₂=1,Nₒ=0

Procedure mencetak_angka;

Deklarasi :

  angka           : integer;

Algoritma :

  Input (angka)

    if angka = 1 then

      output (“satu”)

    else

      if angka = 2 then

        output (“dua”)

      else

        if angka = 3 then

          output (“tiga”)

        else

          if angka = 4 then

            output (“empat”)

         else

           output (“angka yang dimasukkan salah”)

         endif

       endif

     endif

   endif

endprocedure.

Analisis :

Operator = (=)

Tmin(n) = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = 4n

•          Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

4n € O (n²)

4n ≤ 4n+n ( untuk semua n ≥ 1)

4n ≤ 5n

4n ≤ 5n²

C= 5 , Nₒ=1

• Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

4n € Ω (n⁰)

4n ≥ n⁰ (untuk semua n ≥ 1)

C=1 , Nₒ=1

•       Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

4n ≤ n²

C₁=4 ,Nₒ=1

-Batas Akhir

T(n) ≥ (n⁰)

4n ≥ n⁰

C₂=1,Nₒ=1

Tave(n) = (n+4n) / 2 = 5n ₊ 

•          Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

5n+2⁻¹ € O (n²)

5n+2⁻¹ ≤ 5n+n ( untuk semua n ≥ 2 )

5n+2⁻¹  ≤ 6n

6n ≤ 6n²

C= 6 , Nₒ=2

•        Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

5n+2⁻¹  € Ω(n⁻¹)

5n+2⁻¹ ≥ 5n - n (untuk semua n ≥ 1)

5n+2⁻¹ ≥ 4n

4n ≥ 4n⁻¹

C=4 , Nₒ=1

•         Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

5n+2⁻¹  € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

5n+2⁻¹ ≤ 5n +n

5n+2⁻¹ ≤ 6n

6n ≤ 6n²

C₁=6 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

5n+2⁻¹ ≥ 5n – n

5n+2⁻¹ ≥ 4n

 4n ≥ 4n⁻¹

C₂=4,Nₒ=1

Procedure {Menjumlahkan atau mengalikan sebuah bilangan dengan 10, bergantung pada nilai x}

Deklarasi

m : integer

x : integer

Deskripsi

m ← 1

read (x)

while x ≠ 0 do

if x mod 2 then

m ← m+10

else

m ← m*10

endif

read(x)

endwhile

write(m)

Analisis : 

Operator - ←

Tmin(n) = 1

•     Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

1 € O (n²)

1 ≤ 1n² ( untuk semua n ≥ 0)

1 ≤ 1n²

1 ≤ 1n²

C= 1 , Nₒ=0

•    Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

1 € Ω(n⁻¹)

1 ≥ n⁻¹ (untuk semua n ≥ 0) karena n⁰ = 1.

C=1 , Nₒ=0

•        Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

1 € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

1 ≤ n²

C₁=1 ,Nₒ=0

-Batas Akhir

T(n) ≥ n⁻¹

1 ≥ n⁻¹

C₂=1,Nₒ=0

Tmax(n) = n

•         Big O (g(n)) , cari c dan nₒ,sehingga t(n) ≤ C (g(n)) untuk semua n ≥ nₒ

N € O (n²)

N ≤ n+n ( untuk semua n ≥ 1 )

N ≤ 2n

N ≤ 2n²

C= 2 , Nₒ=1

•          Big Ω (g(n)) , cari c dan nₒ ,sehingga t(n) ≥ C (g(n)) untuk semua n ≥ nₒ

N € Ω(n⁻¹)

N ≥ n⁻¹ (untuk semua n ≥ 0)

C=1 , Nₒ=0

•          Big Ѳ (g(n)) , cari c₁ dan c₂ , sehingga c₂ (g(n)) ≤ t(n) ≤ c₁(g(n)) untuk semua n ≥ nₒ

N € Ѳ (g(n))

-Batas Atas

T(n) ≤ n²

N ≤ n²

C₁=1 ,Nₒ=1

-Batas Akhir

T(n) ≥ n⁻¹

N ≥ n⁻¹

C₂=1,Nₒ=0

Tavg(n) :  (1/2n(1+n))/2

 

Adj

Author & Editor

Silahkan Copy Paste Tapi Cantumin Link Sumber Ya kk (^3^) Ok | Kalo Gak Tak Tabok (---)p