Bagaimana cara mengetahui notasi analisis kompleksitas waktu yang digunakan?

Di sebagian besar kelas algoritma pengantar, notasi seperti (Big O) dan diperkenalkan, dan seorang siswa biasanya akan belajar menggunakan salah satu dari ini untuk menemukan kompleksitas waktu. $O$ $\Theta$

Namun, ada notasi lain, seperti , dan . Apakah ada skenario khusus di mana satu notasi lebih disukai daripada yang lain? $o$ $\Omega$ $\omega$

algorithms terminology asymptotics landau-notation reference-question Jack H
sumber

ini tidak begitu disukai seperti yang berlaku ...

vzn

Jawaban:

Anda mengacu pada notasi Landau . Mereka bukan simbol yang berbeda untuk hal yang sama tetapi memiliki makna yang sama sekali berbeda. Yang mana yang "lebih disukai" tergantung sepenuhnya pada pernyataan yang diinginkan.

$f \in \cal{O}(g)$ berarti bahwa tumbuh paling cepat secepat , asimtotik dan hingga faktor konstan; menganggapnya sebagai . adalah bentuk yang lebih ketat, yaitu . $f$ $g$ $\leq$ $f \in o(g)$ $<$

$f \in \Omega(g)$ memiliki makna simetris: tumbuh setidaknya secepat . adalah sepupunya yang lebih ketat. Anda dapat melihat bahwa setara dengan . $f$ $g$ $\omega$ $f \in \Omega(g)$ $g \in \cal{O}(f)$

$f \in \Theta(g)$ berarti bahwa tumbuh sekitar secepat ; secara resmi . (kesetaraan asimptotik) adalah bentuknya yang lebih kuat. Kami sering mengartikan ketika kami menggunakan . $f$ $g$ $f \in \cal{O}(g) \cap \Omega(g)$ $f \sim g$ $\Theta$ $\cal{O}$

Perhatikan bagaimana dan saudara kandungnya adalah kelas fungsi . Penting untuk sangat menyadari hal ini dan definisi mereka yang tepat - yang dapat berbeda tergantung pada siapa yang berbicara - ketika melakukan "aritmatika" dengan mereka. $\cal{O}(g)$

Saat membuktikan sesuatu, berhati-hatilah untuk bekerja dengan definisi Anda yang tepat. Ada banyak definisi untuk simbol Landau di sekitar (semua dengan intuisi dasar yang sama), beberapa di antaranya setara pada beberapa set pada fungsi tetapi tidak pada yang lain.

Bacaan yang disarankan:

Jika Anda tertarik menggunakan notasi Landau dengan cara yang keras dan sehat, Anda mungkin tertarik dengan karya terbaru oleh Rutanen et al. [1]. Mereka merumuskan kriteria yang diperlukan dan cukup untuk notasi asimtotik saat kami menggunakannya dalam algoritmik, menunjukkan bahwa definisi umum gagal memenuhi mereka dan memberikan (yang, pada kenyataannya) definisi yang bisa diterapkan.

Definisi umum notasi-O untuk analisis algoritma oleh K. Rutanen et al. (2015)

Raphael
sumber

Saya hanya ingin menunjukkan bahwa walaupun bertindak seperti dan bertindak seperti , ada perbedaan; tidak sulit menemukan fungsi dan sedemikian rupa sehingga dan .

O

$\mathcal{O}$

\leq

$\le$

Ω

$\Omega$

\geq

$\ge$

g

$g$

f

$f$

f \notin O (g)

$f \not\in \mathcal{O}(g)$

f \notin Ω (g)

$f \not\in \Omega(g)$

Zach Langley

+1 untuk penyebutan kelas fungsi. Hal-hal seperti dan muncul di mana-mana di kertas dan buku, yang dapat membingungkan bagi orang-orang yang menghadapi notasi ini untuk pertama kalinya.

o (1)

$o(1)$

Ω (2^{n})

$\Omega(2^n)$

Janoma

@ZachLangley Apa yang Anda katakan sangat benar. Tidak ada pesanan total di sini. Mungkin berbahaya untuk memunculkan sama sekali, tetapi saya pikir itu melayani tujuan membangun intuisi.

\leq

$\leq$

Raphael

Big O: batas atas

"Big O" ( ) sejauh ini adalah yang paling umum. Ketika Anda menganalisis kompleksitas suatu algoritma, sebagian besar waktu, yang penting adalah memiliki batas atas seberapa cepat waktu berjalan¹ tumbuh ketika ukuran input tumbuh. Pada dasarnya kita ingin tahu bahwa menjalankan algoritma tidak akan memakan waktu “terlalu lama”. Kami tidak dapat mengungkapkan ini dalam satuan waktu aktual (detik), karena itu akan tergantung pada implementasi yang tepat (cara program ditulis, seberapa baik kompiler, seberapa cepat prosesor mesin, ...). Jadi kami mengevaluasi apa yang tidak bergantung pada detail seperti itu, yaitu berapa lama waktu yang diperlukan untuk menjalankan algoritme saat kami memberinya input yang lebih besar. Dan kami sangat peduli ketika kami bisa memastikan bahwa program ini selesai, jadi kami biasanya ingin tahu bahwa ini akan memakan waktu yang begitu lama. $O$

Untuk mengatakan bahwa suatu algoritma memiliki run time untuk ukuran input berarti bahwa ada beberapa konstanta sehingga algoritma menyelesaikan paling banyak langkah , yaitu waktu berjalan algoritma paling banyak tumbuh secepat (hingga faktor penskalaan). Memperhatikan waktu proses algoritma untuk ukuran input , secara informal berarti bahwa hingga beberapa faktor penskalaan. $O(f(n))$ $n$ $K$ $K \, f(n)$ $f$ $T(n)$ $n$ $O(n)$ $T(n) \le f(n)$

Batas bawah

Terkadang, berguna untuk memiliki lebih banyak informasi daripada batas atas. adalah kebalikan dari : itu menyatakan bahwa suatu fungsi tumbuh setidaknya secepat yang lain. berarti bahwa untuk beberapa konstanta , atau secara informal, naik untuk beberapa faktor penskalaan. $\Omega$ $O$ $T(n) = \Omega(g(n))$ $T(N) \ge K' g(n)$ $K'$ $T(n) \ge g(n)$

Ketika waktu berjalan dari algoritma dapat ditentukan secara tepat, menggabungkan dan : itu menyatakan bahwa laju pertumbuhan suatu fungsi diketahui, hingga faktor penskalaan. berarti bahwa untuk beberapa konstanta dan . Secara informal, hingga beberapa faktor penskalaan. $\Theta$ $O$ $\Omega$ $T(n) = \Theta(h(n))$ $K h(n) \ge T(n) \ge K' h(n)$ $K$ $K'$ $T(n) \approx h(n)$

Pertimbangan lebih lanjut

"Little" dan lebih jarang digunakan dalam analisis kompleksitas. Sedikit lebih kuat dari besar ; di mana menunjukkan pertumbuhan yang tidak lebih cepat, menunjukkan bahwa pertumbuhan itu lebih lambat. Sebaliknya, menunjukkan pertumbuhan yang lebih cepat. $o$ $\omega$ $o$ $O$ $O$ $o$ $\omega$

Saya sedikit informal dalam diskusi di atas. Wikipedia memiliki definisi formall dan pendekatan yang lebih matematis.

Perlu diingat bahwa penggunaan tanda sama dengan dan sejenisnya adalah keliru. Sebenarnya, adalah seperangkat fungsi dari variabel , dan kita harus menulis . $T(n) = O(f(n))$ $O(f(n))$ $n$ $T \in O(f)$

Contoh: beberapa algoritma penyortiran

Karena ini agak kering, izinkan saya memberi contoh. Sebagian besar algoritma pengurutan memiliki kuadrat waktu run case terburuk, yaitu untuk input ukuran , run time algoritma adalah . Misalnya, pemilihan sort memiliki waktu berjalan , karena memilih elemen membutuhkan perbandingan , untuk total perbandingan . Bahkan, jumlah perbandingan selalu tepat , yang tumbuh sebagai . Jadi kita bisa lebih tepat tentang kompleksitas waktu dari jenis seleksi: itu adalah . $n$ $O(n^2)$ $O(n^2)$ $k$ $n-k$ $n(n-1)/2$ $n(n-1)/2$ $n^2$ $\Theta(n^2)$

Sekarang ambil semacam penggabungan . Sortir gabungan juga kuadratik ( ). Ini benar, tetapi tidak terlalu tepat. Penggabungan jenis sebenarnya memiliki waktu berjalan dalam kasus terburuk. Seperti pemilihan, aliran pekerjaan gabungan pada dasarnya tidak tergantung pada bentuk input, dan waktu berjalannya selalu hingga faktor multiplikasi konstan, yaitu . $O(n^2)$ $O(n \: \mathrm{lg}(n))$ $n \: \mathrm{lg}(n)$ $\Theta(n \: \mathrm{lg}(n))$

Selanjutnya, pertimbangkan quicksort . Quicksort lebih kompleks. Ini tentu saja . Selain itu, kasus terburuk quicksort adalah kuadrat: kasus terburuk adalah . Namun, kasus quicksort terbaik (ketika input sudah diurutkan) adalah linear: yang terbaik yang bisa kita katakan untuk batas bawah untuk quicksort secara umum adalah . Saya tidak akan mengulangi buktinya di sini, tetapi kompleksitas rata - rata quicksort (rata-rata diambil alih semua kemungkinan permutasi input) adalah . $O(n^2)$ $\Theta(n^2)$ $\Omega(n)$ $\Theta(n \: \mathrm{lg}(n))$

Ada hasil umum tentang kompleksitas pengurutan algoritma dalam pengaturan umum. Asumsikan bahwa algoritma pengurutan hanya dapat membandingkan dua elemen sekaligus, dengan hasil ya-atau-tidak (baik atau ). Maka jelas bahwa waktu berjalan algoritma pengurutan selalu (di mana adalah jumlah elemen untuk disortir), karena algoritma harus membandingkan setiap elemen setidaknya sekali untuk mengetahui di mana ia akan cocok. Batas bawah ini dapat dipenuhi, misalnya, jika input sudah diurutkan dan algoritme hanya membandingkan setiap elemen dengan yang berikutnya dan menyimpannya secara berurutan (yaitu perbandingan ). Apa yang kurang jelas adalah bahwa waktu berjalan maksimum itu perlu $x \le y$ $x > y$ $\Omega(n)$ $n$ $n-1$ $\Omega(n \: \mathrm{lg}(n))$ . Ada kemungkinan bahwa algoritma kadang-kadang akan membuat perbandingan lebih sedikit, tetapi harus ada beberapa konstan sehingga untuk setiap ukuran input , setidaknya ada satu input yang algoritma membuat lebih dari perbandingan. Gagasan buktinya adalah untuk membangun pohon keputusan dari algoritma, yaitu untuk mengikuti keputusan yang diambil algoritma dari hasil setiap perbandingan. Karena setiap perbandingan mengembalikan hasil ya-atau-tidak, pohon keputusan adalah pohon biner. Adakemungkinan permutasi input, dan algoritme perlu membedakan antara semuanya, sehingga ukuran pohon keputusan adalah $K$ $n$ $K n \mathrm{lg}(n)$ $n!$ $n!$ . Karena pohon itu adalah pohon biner, dibutuhkan kedalaman agar sesuai dengan semua node ini. Kedalaman adalah jumlah maksimum keputusan yang diambil algoritma, sehingga menjalankan algoritme setidaknya melibatkan banyak perbandingan ini: waktu lari maksimum adalah . $\Theta(\mathrm{lg}(n!)) = \Theta(n\:\mathrm{lg}(n))$ $\Omega(n \: \mathrm{lg}(n))$

¹ _{Atau konsumsi sumber daya lainnya seperti ruang memori. Dalam jawaban ini, saya hanya mempertimbangkan waktu berjalan.}

Gilles
sumber

"Namun, kasus quicksort terbaik (ketika input sudah disortir) adalah linear" ini adalah kasus terburuk !!

user5507

@ user5507: Sebenarnya, itu tergantung pada strategi pivot. Jika elemen pertama (atau terakhir) dipilih sebagai pivot, maka Anda benar; tetapi jika Anda memilih elemen tengah, atau median input pertama, tengah, terakhir, maka diurutkan adalah kasus terbaik.

chirlu

"O dan ω kecil lebih jarang digunakan dalam analisis kompleksitas." Ini tidak benar dalam analisis kompleksitas ruang. Dalam analisis kompleksitas waktu, Anda biasanya menggunakan o dan ω ketika Anda menghitung operasi tertentu (perbandingan, pencarian disk, kehilangan cache, apa yang Anda miliki). Tetapi karena Anda selalu dapat menunggu dan membeli komputer yang lebih cepat, "waktu dinding" selalu "hingga faktor yang konstan", sehingga O-besar jauh lebih umum. Dalam analisis ruang, sering ada batas bawah keras karena teori informasi, sehingga sangat umum untuk melihat ukuran yang dilaporkan sebagai "f (n) + o (f (n)) bit" di mana f (n) adalah batas bawah.

Nama samaran

Sementara saya memikirkannya: Jika f (n) adalah batas bawah teoretis pada ukuran beberapa struktur data, maka yang menggunakan f (n) + O (1) (overhead konstan) disebut "implisit", yang menggunakan f (n) + O (f (n)) (overhead relatif konstan) disebut "kompak", dan yang menggunakan f (n) + o (f (n)) (overhead relatif menjadi akhirnya tidak signifikan) disebut "ringkas" ". Istilah bagus untuk diketahui jika Anda perlu bekerja di ruang itu.

Nama samaran

Biasanya digunakan untuk menyatakan batas atas (perkiraan dari atas), sedangkan digunakan untuk menyatakan batas bawah (perkiraan dari bawah), dan digunakan ketika mereka cocok, dalam hal ini Anda dapat menggunakan di tempat mereka (biasanya) untuk menyatakan hasilnya. $O$ $\Omega$ $\Theta$ $\Theta$

Kaveh
sumber

"Khas"? Mereka dapat digunakan untuk sesuatu yang lain?

svick

@svick, ya, misalnya yang bukan merupakan pernyataan batas atas. Dengan pernyataan batas atas maksud saya sesuatu seperti yang mengekspresikan batas atas pada .

P = D T i m e (n^{O (1)})

$\mathsf{P} = \mathsf{DTime}(n^{O(1)})$

f = O (g)

$f = O(g)$

f

$f$

Kaveh

Sebenarnya, Kaveh, itu adalah pernyataan batas atas. Terjemahan bahasa Inggris propoer " " adalah "P adalah serangkaian masalah yang dapat diselesaikan dengan menggunakan AT PALING sejumlah operasi polinomial". Jika Anda tidak bermaksud "paling banyak", Anda seharusnya menulis . (Kedua pernyataan itu benar, tentu saja.)

P = D T i m e (n^{O (1)})

$P = DTime(n^{O(1)})$

P = D T i m e (n^{Θ (1)})

$P = DTime(n^{\Theta(1)})$

JeffE

@ Jeff, saya menganggapnya sebagai kesetaraan antara set fungsi, tetapi Anda benar, orang juga bisa menganggapnya sebagai batas atas dalam arti yang lebih umum.

Kaveh

@JeffE Sebenarnya, , karena tetapi .

P \neq D T I M E (n^{Θ (1)})

$\mathrm{P}\neq \mathrm{DTIME}(n^{\Theta(1)})$

D T I M E (Θ (n \log n)) \subset P

$\mathrm{DTIME}(\Theta(n\log n))\subset \mathrm{P}$

D T I M E (Θ (n \log n)) \cap D T I M E (n^{Θ (1)}) = \emptyset

$\mathrm{DTIME}(\Theta(n\log n))\cap\mathrm{DTIME}(n^{\Theta(1)})=\emptyset$

David Richerby