Efisiensi Algoritma: Kompleksitas Waktu dan Ruang

Konsep dalam Ilmu Komputer

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Pengenalan Notasi Big-O

  • Mengukur pertumbuhan waktu dan ruang saat input membesar
  • Contoh: $O(n)$, $O(n^2)$, $O(log\, n)$
  • 'O' menyatakan orde pertumbuhan, mis. O(n) = linear
Konsep dalam Ilmu Komputer

Kompleksitas waktu - analogi kantor

Bagan yang menunjukkan berbagai Kompleksitas Notasi Big O

  • $O(1)$ - waktu konstan - "Sekilas cepat" - "konstan"
  • $O(log\,n)$ - kenaikan waktu lambat - "Membagi tumpukan" - "logaritmik"
  • $O(n)$ - kenaikan linear - "Membaca dokumen" - "linear"
  • $O(n\,log\,n)$ - kenaikan waktu lebih cepat - "Mengurut tumpukan" - "linieritmik"
  • $O(n^2)$ - kenaikan kuadratik - "Membandingkan dokumen" - "kuadratik"
Konsep dalam Ilmu Komputer

Kompleksitas ruang - analogi kantor

Bagan yang menunjukkan berbagai Kompleksitas Notasi Big O

  • $O(1)$ - ruang konstan - "Ruang meja" - "konstan"
  • $O(log\,n)$ - kenaikan ruang lambat - "catatan minimal" - "logaritmik"
  • $O(n)$ - kenaikan linear - "sticky notes" - "linear"
  • $O(n\,log\,n)$ - kenaikan ruang lebih cepat - "Tumpukan sementara" - "linieritmik"
  • $O(n^2)$ - kenaikan ruang kuadratik - "grid perbandingan" - "kuadratik"
Konsep dalam Ilmu Komputer

Ayo berlatih!

Konsep dalam Ilmu Komputer

Preparing Video For Download...