Apa itu O (...) dan bagaimana cara menghitungnya?

31

Membantu! Saya punya pertanyaan di mana saya perlu menganalisis Big-O suatu algoritma atau beberapa kode.

  • Saya tidak yakin apa Big-O itu atau bagaimana hubungannya dengan Big-Theta atau cara lain untuk menganalisis kompleksitas suatu algoritma.

  • Saya tidak yakin apakah Big-O mengacu pada waktu untuk menjalankan kode, atau jumlah memori yang dibutuhkan (space / time tradeoffs).

  • Saya memiliki pekerjaan rumah Ilmu Komputer di mana saya perlu mengambil beberapa loop, mungkin algoritma rekursif, dan muncul dengan Big-O untuk itu.

  • Saya sedang mengerjakan sebuah program di mana saya memiliki pilihan antara dua struktur data atau algoritma dengan Big-O yang dikenal, dan tidak yakin mana yang harus dipilih.

Bagaimana saya memahami cara menghitung dan menerapkan Big-O untuk program saya, pekerjaan rumah, atau pengetahuan umum Ilmu Komputer?

Catatan: pertanyaan ini adalah target dupe kanonik untuk pertanyaan Big-O lainnya yang ditentukan oleh komunitas . Ini sengaja luas untuk dapat berisi sejumlah besar informasi yang berguna untuk banyak pertanyaan Big-O. Tolong jangan gunakan fakta bahwa ini seluas ini sebagai indikasi bahwa pertanyaan serupa dapat diterima.

algorithms complexity big-o tidak diketahui
sumber
1
Sekedar catatan, pertanyaan ini sedang dibahas pada meta di sini .
enderland
2
Sumber yang bagus untuk memulai adalah kursus akademi Khan (Thomas Cormen dari CLRS adalah salah satu penulisnya). Ini juga sumber yang bagus bagi saya sebagai lulusan CS. khanacademy.org/computing/computer-science/algorithms
Sudip Bhandari
3
Kepada orang yang menandai pertanyaan ini: baca subteks di bagian bawah pertanyaan, dan ikuti tautan itu sebelum menandai atau memberi suara untuk menutup.

Jawaban:

22

O (...) mengacu pada notasi Big-O, yang merupakan cara sederhana untuk menggambarkan berapa banyak operasi yang dibutuhkan suatu algoritma untuk melakukan sesuatu. Ini dikenal sebagai kompleksitas waktu .

Dalam notasi Big-O, biaya suatu algoritma diwakili oleh operasi yang paling mahal pada jumlah besar. Jika suatu algoritma mengambil langkah - langkah, itu akan diwakili O (n 3 ). Algoritma yang menghitung setiap item dalam daftar akan beroperasi dalam waktu O (n), yang disebut waktu linear.n3 + n2 + n

Untuk daftar nama dan contoh klasik di Wikipedia: Urutan fungsi umum

Bahan terkait:

MaxGabriel
sumber
6
Catatan: big O tidak secara inheren mengukur waktu atau ruang atau hal tertentu. Ini hanya membatasi pertumbuhan asimptotik dari suatu fungsi (hingga konstan). Fungsi itu bisa berupa waktu, ruang, dll. Dari suatu algoritma sebagai fungsi dari panjang inputnya, dan yang paling umum dalam konteks CS adalah waktunya, tetapi belum tentu.
Pasang kembali Monica
23

Apa fungsi asimptotik? Apa itu asimptot?

Diberikan fungsi f (n) yang menggambarkan jumlah sumber daya (waktu CPU, RAM, ruang disk, dll) yang dikonsumsi oleh suatu algoritma ketika diterapkan pada input ukuran n , kami menetapkan hingga tiga notasi asimtotik untuk menggambarkan kinerjanya untuk besar n .

Sebuah asimtot (atau fungsi asymptotic) hanya beberapa fungsi lain (atau relasi) g (n) yang f (n) mendapat semakin dekat sebagai n tumbuh lebih besar dan lebih besar, tetapi tidak pernah cukup mencapai. Keuntungan dari berbicara tentang fungsi asimptotik adalah bahwa mereka umumnya lebih mudah untuk dibicarakan walaupun jika ekspresi untuk f (n) sangat rumit. Fungsi asimptotik digunakan sebagai bagian dari notasi pembatas yang membatasi f (n) di atas atau di bawah.

(Catatan: dalam arti yang digunakan di sini, fungsi asimptotik hanya dekat dengan fungsi asli setelah mengoreksi beberapa faktor bukan-nol yang konstan, karena ketiga notasi O-Θ / Ω besar mengabaikan faktor-faktor konstan ini dari pertimbangan mereka.)

Apa tiga notasi pembatas asimptotik dan bagaimana perbedaannya?

Ketiga notasi digunakan seperti ini:

f (n) = O (g (n))

di mana f (n) di sini adalah fungsi yang menarik, dan g (n) adalah beberapa fungsi asimptotik lain yang Anda coba perkirakan mendekati f (n) dengan. Ini tidak boleh dianggap sebagai persamaan dalam arti yang ketat, tetapi pernyataan formal antara seberapa cepat f (n) tumbuh sehubungan dengan n dibandingkan dengan g (n) , karena n menjadi besar. Puritan akan sering menggunakan notasi alternatif f (n) ∈ O (g (n)) untuk menekankan bahwa simbol O (g (n)) benar-benar seluruh keluarga fungsi yang memiliki tingkat pertumbuhan yang sama.

Notasi Big-Th (Theta) menyatakan persamaan pada pertumbuhan f (n) hingga faktor konstan (lebih lanjut tentang ini nanti). Berperilaku mirip dengan =operator untuk tingkat pertumbuhan.

Notasi O besar menggambarkan batas atas pada pertumbuhan f (n) . Berperilaku mirip dengan ≤operator untuk tingkat pertumbuhan.

Notasi Big-Omega (Omega) menggambarkan batas bawah pada pertumbuhan f (n) . Berperilaku mirip dengan ≥operator untuk tingkat pertumbuhan.

Ada banyak notasi asimptotik lainnya , tetapi notasi ini tidak muncul sesering dalam literatur ilmu komputer.

Notasi-O besar dan sejenisnya seringkali sebagai cara untuk membandingkan kompleksitas waktu .

Apa itu kompleksitas waktu?

Kompleksitas waktu adalah istilah umum untuk jumlah waktu T (n) yang diperlukan untuk suatu algoritma untuk mengeksekusi sebagai fungsi dari ukuran inputnya n . Ini dapat diukur dalam jumlah waktu nyata (misalnya detik), jumlah instruksi CPU, dll. Biasanya diasumsikan bahwa algoritma akan berjalan pada komputer arsitektur von Neumann Anda sehari-hari . Tetapi tentu saja Anda dapat menggunakan kompleksitas waktu untuk berbicara tentang sistem komputasi yang lebih eksotis, di mana segalanya mungkin berbeda!

Juga umum untuk berbicara tentang kompleksitas ruang menggunakan notasi Big-O. Kompleksitas ruang adalah jumlah memori (penyimpanan) yang diperlukan untuk menyelesaikan algoritme, yang bisa berupa RAM, disk, dll.

Mungkin satu algoritma lebih lambat tetapi menggunakan lebih sedikit memori, sedangkan yang lain lebih cepat tetapi menggunakan lebih banyak memori. Masing-masing mungkin lebih tepat dalam keadaan yang berbeda, jika sumber daya dibatasi secara berbeda. Misalnya, prosesor yang disematkan mungkin memiliki memori terbatas dan mendukung algoritma yang lebih lambat, sementara server di pusat data mungkin memiliki jumlah memori yang besar dan mendukung algoritma yang lebih cepat.

Menghitung Besar ϴ

Menghitung Big ϴ dari suatu algoritma adalah topik yang dapat mengisi buku teks kecil atau kira-kira setengah semester dari kelas sarjana: bagian ini akan membahas dasar-dasarnya.

Diberi fungsi f (n) dalam pseudocode:

int f(n) {
  int x = 0;
  for (int i = 1 to n) {
    for (int j = 1 to n) {
      ++x;
    }
  }
  return x;
}

Apa kompleksitas waktu?

Loop luar berjalan n kali. Untuk setiap kali loop luar berjalan, loop dalam berjalan n kali. Ini menempatkan waktu berjalan pada T (n) = n 2 .

Pertimbangkan fungsi kedua:

int g(n) {
  int x = 0;
  for (int k = 1 to 2) {
    for (int i = 1 to n) {
      for (int j = 1 to n) {
        ++x;
      }
    }
  }
  return x;
}

Loop luar berjalan dua kali. Loop tengah berjalan n kali. Untuk setiap kali loop tengah berjalan, loop dalam berjalan n kali. Ini menempatkan waktu berjalan pada T (n) = 2n 2 .

Sekarang pertanyaannya adalah, apa waktu berjalan asimptotik dari kedua fungsi?

Untuk menghitung ini, kami melakukan dua langkah:

  • Hapus konstanta. Karena algoritma meningkat dalam waktu karena input, istilah lain mendominasi waktu berjalan, menjadikannya tidak penting.
  • Hapus semua kecuali istilah terbesar. Saat n menuju tak terhingga, n 2 dengan cepat melampaui n .

Kunci mereka di sini adalah fokus pada istilah yang dominan, dan menyederhanakan istilah itu .

T (n) = n 2 ∈ ϴ (n 2 )
T (n) = 2n 2 ∈ ϴ (n 2 )

Jika kami memiliki algoritma lain dengan beberapa istilah, kami akan menyederhanakannya menggunakan aturan yang sama:

T (n) = 2n 2 + 4n + 7 ∈ ϴ (n 2 )

Kuncinya dengan semua algoritme ini adalah kami fokus pada istilah terbesar dan menghapus konstanta . Kami tidak melihat waktu berjalan sebenarnya, tetapi kompleksitas relatif .

Menghitung Big-Ω dan Big-O

Pertama, berhati-hatilah bahwa dalam literatur informal , "Big-O" sering dianggap sebagai sinonim untuk Big-Θ, mungkin karena huruf-huruf Yunani sulit diketik. Jadi jika seseorang tiba-tiba meminta Anda untuk Big-O suatu algoritma, mereka mungkin ingin Big-Θ nya.

Sekarang jika Anda benar-benar ingin menghitung Big-Ω dan Big-O dalam pengertian formal yang didefinisikan sebelumnya, Anda memiliki masalah besar: ada banyak deskripsi Big-Ω dan Big-O yang tak terhingga untuk setiap fungsi yang diberikan! Ini seperti bertanya berapa angka yang kurang dari atau sama dengan 42. Ada banyak kemungkinan.

Untuk algoritme dengan T (n) ϴ n (n 2 ) , salah satu dari yang berikut ini adalah pernyataan yang sah secara formal untuk dibuat:

  • T (n) ∈ O (n 2 )
  • T (n) ∈ O (n 3 )
  • T (n) ∈ O (n 5 )
  • T (n) ∈ O (n 12345 × e n )
  • T (n) ∈ Ω (n 2 )
  • T (n) ∈ Ω (n)
  • T (n) ∈ Ω (log (n))
  • T (n) ∈ Ω (log (log (n))))
  • T (n) ∈ Ω (1)

Tetapi tidak benar untuk menyatakan T (n) ∈ O (n) atau T (n) ∈ Ω (n 3 ) .

Apa itu kompleksitas relatif? Kelas algoritma apa saja yang ada?

Jika kita membandingkan dua algoritma yang berbeda, kompleksitasnya saat input menuju infinity biasanya akan meningkat. Jika kita melihat berbagai jenis algoritma, mereka mungkin tetap relatif sama (katakanlah, berbeda dengan faktor konstan) atau dapat sangat berbeda. Ini adalah alasan untuk melakukan analisis Big-O: untuk menentukan apakah suatu algoritma akan berkinerja wajar dengan input besar.

Kelas-kelas algoritma memecah sebagai berikut:

  • Θ (1) - konstan. Misalnya, memilih nomor pertama dalam daftar akan selalu memakan waktu yang sama.

  • Θ (n) - linear. Misalnya, iterasi daftar akan selalu memakan waktu sebanding dengan ukuran daftar, n .

  • Θ (log (n)) - logaritmik (basis biasanya tidak masalah). Algoritma yang membagi ruang input pada setiap langkah, seperti pencarian biner, adalah contohnya.

  • Θ (n × log (n)) - waktu linear logaritmik (“linearitmik”). Algoritma ini biasanya membagi dan menaklukkan ( log (n) ) sambil tetap mengulangi ( n ) semua input. Banyak algoritme pengurutan yang populer (gabungan, Timsort) termasuk dalam kategori ini.

  • Θ (n m ) - polinomial ( n dinaikkan ke konstanta m ). Ini adalah kelas kompleksitas yang sangat umum, sering ditemukan di loop bersarang.

  • Θ (m n ) - eksponensial (setiap konstan m diangkat ke n ). Banyak algoritma rekursif dan grafik termasuk dalam kategori ini.

  • Θ (n!) - faktorial. Grafik dan algoritma kombinatorial tertentu adalah kompleksitas faktorial.

Apakah ini ada hubungannya dengan kasus terbaik / rata-rata / terburuk?

Tidak. Big-O dan keluarga notasinya berbicara tentang fungsi matematika tertentu . Mereka adalah alat matematika yang digunakan untuk membantu mengkarakterisasi efisiensi algoritma, tetapi gagasan terbaik / rata-rata / kasus terburuk tidak terkait dengan teori tingkat pertumbuhan yang dijelaskan di sini.

Untuk berbicara tentang Big-O suatu algoritma, seseorang harus berkomitmen pada model matematika tertentu dari suatu algoritma dengan tepat satu parameter n, yang seharusnya menggambarkan "ukuran" dari input, dalam arti apa pun berguna. Tetapi di dunia nyata, input memiliki struktur lebih dari sekadar panjangnya. Jika ini adalah algoritma sorting, saya bisa memberi makan dalam string "abcdef", "fedcba"atau "dbafce". Semua dari mereka memiliki panjang 6, tetapi salah satunya sudah disortir, satu terbalik, dan yang terakhir hanya campur aduk acak. Beberapa algoritma pengurutan (seperti Timsort) berfungsi lebih baik jika inputnya sudah diurutkan. Tetapi bagaimana seseorang memasukkan ketidakhomogenan ini ke dalam model matematika?

Pendekatan tipikal adalah mengasumsikan input berasal dari beberapa distribusi probabilistik acak. Kemudian, Anda meratakan kompleksitas algoritme untuk semua input dengan panjang n. Ini memberi Anda model kompleksitas kasus rata-rata dari algoritma. Dari sini, Anda dapat menggunakan notasi Big-O / Θ / as seperti biasa untuk menggambarkan perilaku kasus rata-rata.

Tetapi jika Anda khawatir tentang serangan penolakan layanan, maka Anda mungkin harus lebih pesimis. Dalam hal ini, lebih aman untuk mengasumsikan bahwa satu - satunya input adalah mereka yang paling banyak menyebabkan kesedihan pada algoritma Anda. Ini memberi Anda model kompleksitas kasus terburuk dari algoritma. Setelah itu, Anda dapat berbicara tentang Big-O / Θ / Ω dll dari model terburuk .

Demikian pula, Anda juga dapat memfokuskan minat Anda secara eksklusif pada input yang algoritme Anda memiliki paling sedikit masalah untuk sampai pada model kasus terbaik , kemudian lihat Big-O / Θ / Ω dll.

pengguna22815
sumber
Ini adalah jawaban yang bagus, tetapi Big-O dan Big-little tidak ada hubungannya dengan kasus terburuk dan terbaik. Mereka adalah batas atas dan bawah, tetapi keduanya dapat berlaku untuk kedua kasus, misalnya, jenis penyisipan, dalam kasus terbaik, memiliki kompleksitas waktu ϴ(n)(baik Big-O dan Big-Ω) sambil memiliki, dalam kasus terburuk, kompleksitas waktu ϴ(n²)(baik Big-O dan Big-Ω).
Paulus
Juga, algoritma apa pun, kecuali algoritma kosong, ada Ω(1)dalam kasus terbaik, terburuk, dan rata-rata, tetapi itu karena itu adalah batas bawah dan tidak ada hubungannya dengan kasus terbaik sebenarnya dari algoritma.
Paul
Besar - apa pun yang tidak ada hubungannya dengan kasus terbaik atau terburuk - ini adalah kesalahpahaman umum. Mereka hanyalah cara untuk menyatakan apakah fungsi deterministik tumbuh lebih cepat, lebih lambat, atau pada tingkat yang sama dibandingkan dengan yang lain. Gagasan terbaik / terburuk hanya ada setelah Anda mulai berbicara tentang kompleksitas ruang / waktu dari algoritma nyata, dalam hal ini faktor-faktor non-deterministik muncul dan Anda perlu mempertimbangkan distribusi probabilitas input Anda. Meski begitu, kasus terbaik / terburuk terletak pada sumbu ortogonal hingga O-Omega besar.
Rufflewind
@Rufflewind jika Anda pikir Anda bisa menggambarkannya dengan lebih baik, maka silakan. Anda sadar ini adalah jawaban komunitas wiki, bukan?
"Pertama, diperingatkan bahwa dalam literatur informal," Big-O "sering diperlakukan sebagai sinonim untuk Big-Θ" -> Tidak hanya dalam literatur informal. Semester pertama saya tentang Kompleksitas, di perguruan tinggi, mengajarkan kepada kami definisi Big-O seolah-olah itu Big-Θ. (Buku teks kami menggunakan definisi itu!) Itu membingungkan saya ketika saya pergi ke Complexity II dan saya menemukan keduanya tidak sama.
T. Sar - Reinstate Monica