Pertanyaan Apa yang dimaksud dengan penjelasan bahasa Inggris biasa dari notasi “Big O”?


Saya lebih memilih definisi formal sesedikit mungkin dan matematika sederhana.


4529
2018-01-28 11:10


asal


Jawaban:


Catatan singkat, ini hampir pasti membingungkan Notasi O besar (yang merupakan batas atas) dengan notasi Theta (yang merupakan dua sisi terikat). Dalam pengalaman saya, ini sebenarnya khas diskusi dalam pengaturan non-akademik. Permintaan maaf untuk kebingungan apa pun yang disebabkan.


Kerumitan O besar dapat divisualisasikan dengan grafik ini:

Big O Analysis

Definisi paling sederhana yang bisa saya berikan untuk notasi Big-O adalah ini:

Notasi Big-O adalah representasi relatif dari kompleksitas suatu algoritma.

Ada beberapa kata yang penting dan sengaja dipilih dalam kalimat itu:

  • relatif: Anda hanya dapat membandingkan apel dengan apel. Anda tidak dapat membandingkan suatu algoritma untuk melakukan perkalian aritmatika ke suatu algoritma yang mengurutkan daftar bilangan bulat. Tetapi perbandingan dua algoritma untuk melakukan operasi aritmatika (satu perkalian, satu tambahan) akan memberi tahu Anda sesuatu yang berarti;
  • perwakilan: Big-O (dalam bentuk yang paling sederhana) mengurangi perbandingan antara algoritma ke variabel tunggal. Variabel itu dipilih berdasarkan pengamatan atau asumsi. Sebagai contoh, algoritma pengurutan biasanya dibandingkan berdasarkan operasi perbandingan (membandingkan dua node untuk menentukan pemesanan relatif mereka). Ini mengasumsikan bahwa perbandingan itu mahal. Tetapi bagaimana jika perbandingan itu murah tapi swapping itu mahal? Itu mengubah perbandingan; dan
  • kompleksitas: jika saya membutuhkan waktu satu detik untuk menyortir 10.000 elemen, berapa lama saya perlu menyortir satu juta? Kompleksitas dalam hal ini adalah ukuran relatif untuk sesuatu yang lain.

Kembalilah dan baca kembali di atas ketika Anda telah membaca sisanya.

Contoh terbaik Big-O yang dapat saya pikirkan adalah melakukan aritmatika. Ambil dua nomor (123456 dan 789012). Operasi aritmatika dasar yang kami pelajari di sekolah adalah:

  • tambahan;
  • pengurangan;
  • perkalian; dan
  • divisi.

Masing-masing merupakan operasi atau masalah. Metode pemecahan ini disebut an algoritma.

Selain itu yang paling sederhana. Anda membariskan angka-angka ke atas (ke kanan) dan menambahkan angka-angka dalam kolom yang menulis nomor terakhir dari penambahan itu dalam hasil. Bagian 'puluhan' dari angka itu dibawa ke kolom berikutnya.

Mari kita asumsikan bahwa penambahan angka-angka ini adalah operasi paling mahal dalam algoritma ini. Masuk akal bahwa untuk menambahkan dua angka ini bersama-sama kita harus menambahkan 6 digit (dan mungkin membawa 7). Jika kita menambahkan dua nomor 100 digit bersama-sama kita harus melakukan 100 tambahan. Jika kita tambahkan dua 10.000 digit angka yang harus kita lakukan 10.000 tambahan.

Lihat polanya? Itu kompleksitas (menjadi jumlah operasi) berbanding lurus dengan jumlah digit n dalam jumlah yang lebih besar. Kami menyebutnya Di) atau kompleksitas linier.

Pengurangan serupa (kecuali Anda mungkin perlu meminjam, bukan membawa).

Perkalian itu berbeda. Anda baris angka, mengambil digit pertama di nomor bawah dan kalikan pada setiap digit di nomor atas dan seterusnya melalui setiap digit. Jadi untuk melipatgandakan dua angka 6 digit, kita harus melakukan 36 perkalian. Kami mungkin perlu menambahkan sebanyak 10 atau 11 kolom untuk mendapatkan hasil akhir juga.

Jika kita memiliki dua nomor 100-digit, kita perlu melakukan 10.000 perkalian dan 200 tambah. Untuk dua satu juta digit angka yang perlu kita lakukan satu triliun (1012) perkalian dan dua juta menambahkan.

Ketika skala algoritma dengan n-kuadrat, ini adalah Di2) atau kompleksitas kuadratik. Ini adalah saat yang tepat untuk memperkenalkan konsep penting lainnya:

Kami hanya peduli dengan bagian kompleksitas yang paling signifikan.

Si cerdik mungkin telah menyadari bahwa kita dapat menyatakan jumlah operasi sebagai: n2 + 2n. Tapi seperti yang Anda lihat dari contoh kami dengan dua angka satu juta digit masing-masing, istilah kedua (2n) menjadi tidak signifikan (terhitung 0,0002% dari total operasi pada tahap itu).

Kita dapat melihat bahwa kita telah mengasumsikan skenario terburuk di sini. Sementara mengalikan 6 angka digit jika salah satunya adalah 4 digit dan yang lainnya 6 digit, maka kita hanya memiliki 24 perkalian. Masih kami menghitung skenario terburuk untuk itu 'n', yaitu ketika keduanya 6 digit angka. Oleh karena itu notasi Big-O adalah tentang skenario kasus terburuk dari suatu algoritma

Buku Telepon

Contoh terbaik berikutnya yang dapat saya pikirkan adalah buku telepon, biasanya disebut Halaman Putih atau serupa tetapi itu akan bervariasi dari satu negara ke negara. Tapi saya sedang berbicara tentang salah satu yang mendaftar orang dengan nama keluarga dan kemudian inisial atau nama depan, mungkin alamat dan kemudian nomor telepon.

Sekarang jika Anda menginstruksikan komputer untuk mencari nomor telepon untuk "John Smith" di buku telepon yang berisi 1.000.000 nama, apa yang akan Anda lakukan? Mengabaikan fakta bahwa Anda dapat menebak seberapa jauh dalam S dimulai (mari kita asumsikan Anda tidak bisa), apa yang akan Anda lakukan?

Implementasi tipikal mungkin membuka ke tengah, mengambil 500.000th dan bandingkan dengan "Smith". Jika kebetulan adalah "Smith, John", kita baru saja beruntung. Jauh lebih mungkin adalah bahwa "John Smith" akan menjadi sebelum atau sesudah nama itu. Jika setelah kami kemudian membagi setengah bagian terakhir dari buku telepon menjadi dua dan ulangi. Jika sebelum itu kita membagi paruh pertama buku telepon menjadi dua dan ulangi. Dan seterusnya.

Ini disebut a pencarian biner dan digunakan setiap hari dalam memprogram apakah Anda menyadarinya atau tidak.

Jadi, jika Anda ingin menemukan nama di buku telepon dari satu juta nama Anda benar-benar dapat menemukan nama apa pun dengan melakukan ini paling banyak 20 kali. Dalam membandingkan algoritma pencarian kami memutuskan bahwa perbandingan ini adalah 'n' kami.

  • Untuk buku telepon 3 nama dibutuhkan 2 perbandingan (paling banyak).
  • Untuk 7 dibutuhkan paling banyak 3.
  • Untuk 15 dibutuhkan 4.
  • ...
  • Untuk 1.000.000 dibutuhkan 20.

Itu sangat bagus bukan?

Dalam istilah Big-O ini O (log n) atau kompleksitas logaritmik. Sekarang logaritma yang dimaksud dapat berupa ln (basis e), log10, log2 atau basis lainnya. Tidak masalah itu masih O (log n) seperti O (2n2) dan O (100n2) masih keduanya O (n2).

Ini bermanfaat pada titik ini untuk menjelaskan bahwa Big O dapat digunakan untuk menentukan tiga kasus dengan algoritma:

  • Kasus terbaik: Dalam pencarian buku telepon, kasus terbaik adalah kita menemukan nama itu dalam satu perbandingan. Ini adalah O (1) atau kompleksitas konstan;
  • Kasus yang Diharapkan: Sebagaimana dibahas di atas, ini adalah O (log n); dan
  • Kasus terburuk: Ini juga O (log n).

Biasanya kami tidak peduli dengan kasus terbaik. Kami tertarik dengan kasus yang diharapkan dan terburuk. Terkadang salah satu dari ini akan menjadi lebih penting.

Kembali ke buku telepon.

Bagaimana jika Anda memiliki nomor telepon dan ingin mencari nama? Polisi memiliki buku telepon terbalik tetapi pencarian tersebut ditolak untuk masyarakat umum. Atau apakah mereka? Secara teknis Anda dapat membalikkan nomor pencarian di buku telepon biasa. Bagaimana?

Anda mulai dengan nama depan dan bandingkan nomornya. Jika itu pertandingan, bagus, jika tidak, Anda melanjutkan ke yang berikutnya. Anda harus melakukannya dengan cara ini karena buku telepon tidak dipesan (melalui nomor telepon).

Jadi untuk menemukan nama yang diberikan nomor telepon (pencarian terbalik):

  • Kasus terbaik: O (1);
  • Kasus yang Diharapkan: O (n) (untuk 500.000); dan
  • Kasus terburuk: O (n) (untuk 1.000.000).

The Travelling Salesman

Ini adalah masalah yang cukup terkenal dalam ilmu komputer dan patut disebutkan. Dalam masalah ini Anda memiliki kota N. Masing-masing kota tersebut terkait dengan 1 atau lebih kota-kota lain dengan jalan jarak tertentu. Masalah Travelling Salesman adalah menemukan tur terpendek yang mengunjungi setiap kota.

Kedengarannya sederhana? Pikirkan lagi.

Jika Anda memiliki 3 kota A, B, dan C dengan jalan di antara semua pasangan maka Anda dapat pergi:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Yah sebenarnya ada kurang dari itu karena beberapa di antaranya setara (A → B → C dan C → B → A adalah setara, misalnya, karena mereka menggunakan jalan yang sama, hanya sebaliknya).

Sebenarnya ada 3 kemungkinan.

  • Bawa ini ke 4 kota dan Anda memiliki (iirc) 12 kemungkinan.
  • Dengan 5 itu 60.
  • 6 menjadi 360.

Ini adalah fungsi dari operasi matematika yang disebut a faktorial. Pada dasarnya:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • ...
  • 25! = 25 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 1064

Jadi Big-O masalah Travelling Salesman Di!) atau kompleksitas faktorial atau kombinatorial.

Pada saat Anda mencapai 200 kota, tidak ada cukup waktu di alam semesta untuk menyelesaikan masalah dengan komputer tradisional.

Sesuatu untuk dipikirkan.

Waktu Polinomial

Hal lain yang ingin saya sampaikan dengan cepat adalah setiap algoritma yang memiliki kompleksitas DiSebuah) dikatakan memiliki kompleksitas polinomial atau dapat dipecahkan waktu polinomial.

O (n), O (n2) dll semua waktu polinomial. Beberapa masalah tidak dapat diselesaikan dalam waktu polinomial. Hal-hal tertentu digunakan di dunia karena ini. Public Key Cryptography adalah contoh utama. Sangat sulit untuk menemukan dua faktor prima dari jumlah yang sangat besar. Jika tidak, kami tidak bisa menggunakan sistem kunci publik yang kami gunakan.

Pokoknya, itu untuk penjelasan saya (semoga sederhana bahasa Inggris) dari Big O (direvisi).


6089
2018-01-28 11:18



Ini menunjukkan bagaimana skala algoritma.

Di2): dikenal sebagai Kompleksitas kuadratik

  • 1 item: 1 detik
  • 10 item: 100 detik
  • 100 item: 10000 detik

Perhatikan bahwa jumlah barang meningkat dengan faktor 10, tetapi waktu meningkat dengan faktor 102. Pada dasarnya, n = 10 dan begitu O (n2) memberi kita faktor skala n2 yaitu 102.

Di): dikenal sebagai Kerumitan linier

  • 1 item: 1 detik
  • 10 item: 10 detik
  • 100 item: 100 detik

Kali ini jumlah barang meningkat dengan faktor 10, dan begitu juga waktu. n = 10 dan faktor penskalaan O (n) adalah 10.

O (1): dikenal sebagai Kerumitan yang konstan

  • 1 item: 1 detik
  • 10 item: 1 detik
  • 100 item: 1 detik

Jumlah item masih meningkat dengan faktor 10, tetapi faktor skala O (1) selalu 1.

O (log n): dikenal sebagai Kompleksitas Logarithmic

  • 1 item: 1 detik
  • 10 item: 2 detik
  • 100 item: 3 detik
  • 1000 item: 4 detik
  • 10.000 item: 5 detik

Jumlah perhitungan hanya ditingkatkan oleh log dari nilai input. Jadi dalam hal ini, dengan asumsi setiap perhitungan membutuhkan waktu 1 detik, log dari input n adalah waktu yang dibutuhkan, karenanya log n.

Itulah intinya. Mereka mengurangi matematika sehingga mungkin tidak persis n2 atau apa pun yang mereka katakan, tetapi itu akan menjadi faktor yang mendominasi dalam penskalaan.


662
2018-01-28 11:28



Notasi Big-O (juga disebut notasi pertumbuhan asimtotik) adalah apa fungsi "terlihat seperti" ketika Anda mengabaikan faktor konstan dan barang-barang dekat asal. Kami menggunakannya untuk dibicarakan bagaimana skala hal.


Dasar-dasar

untuk "cukup banyak masukan" ...

  • f(x) ∈ O(upperbound) cara f "tumbuh tidak lebih cepat dari" upperbound
  • f(x) ∈ Ɵ(justlikethis) berarti f "Tumbuh persis seperti" justlikethis
  • f(x) ∈ Ω(lowerbound) cara f "tumbuh tidak lebih lambat dari" lowerbound

notasi big-O tidak peduli dengan faktor konstan: fungsi 9x² Dikatakan "tumbuh persis seperti" 10x². Tidak juga big-O asymptotic perhatian notasi tentang tidak asimtotik barang ("barang dekat asal" atau "apa yang terjadi ketika ukuran masalah kecil"): fungsi 10x² Dikatakan "tumbuh persis seperti" 10x² - x + 2.

Mengapa Anda ingin mengabaikan bagian yang lebih kecil dari persamaan? Karena mereka menjadi sangat dikerdilkan oleh bagian besar dari persamaan saat Anda mempertimbangkan skala yang lebih besar dan lebih besar; kontribusi mereka menjadi kerdil dan tidak relevan. (Lihat bagian contoh.)

Dengan kata lain, ini semua tentang perbandingan ketika Anda pergi ke infinity. Jika Anda membagi waktu aktual yang dibutuhkan oleh O(...), Anda akan mendapatkan faktor konstan dalam batas input besar. Secara intuitif ini masuk akal: fungsi "skala seperti" satu sama lain jika Anda dapat mengalikan satu untuk mendapatkan yang lain. Artinya, ketika kita mengatakan ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... ini artinya itu untuk ukuran masalah "cukup besar" N (jika kita mengabaikan hal-hal di dekat asal), terdapat beberapa konstanta (misalnya 2,5, benar-benar dibuat) sehingga:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Ada banyak pilihan konstan; seringkali pilihan "terbaik" dikenal sebagai "faktor konstan" dari algoritma ... tetapi kita sering mengabaikannya seperti kita mengabaikan istilah yang tidak terbesar (lihat bagian Faktor Konstan mengapa tidak biasanya penting). Anda juga bisa memikirkan persamaan di atas sebagai terikat, mengatakan "Dalam skenario terburuk, waktu yang dibutuhkan tidak akan pernah lebih buruk daripada kira-kira N*log(N), dalam faktor 2,5 (faktor konstan yang tidak terlalu kami pedulikan)".

Secara umum, O(...) adalah yang paling berguna karena kita sering peduli dengan perilaku terburuk. Jika f(x) mewakili sesuatu yang "buruk" seperti prosesor atau penggunaan memori, lalu "f(x) ∈ O(upperbound)"berarti"upperbound adalah skenario terburuk dari penggunaan prosesor / memori ".


Aplikasi

Sebagai konstruksi matematika murni, notasi big-O tidak terbatas pada berbicara tentang waktu pemrosesan dan memori. Anda dapat menggunakannya untuk mendiskusikan asimtotik apa pun yang skalanya bermakna, seperti:

  • jumlah kemungkinan jabat tangan di antara N orang-orang di sebuah pesta (Ɵ(N²), secara khusus N(N-1)/2, tapi yang penting adalah "skala seperti" )
  • probabilistik jumlah orang yang telah melihat beberapa viral marketing sebagai fungsi waktu
  • bagaimana skala latensi situs web dengan jumlah unit pemrosesan dalam CPU atau GPU atau kluster komputer
  • bagaimana skala output panas pada CPU mati sebagai fungsi dari jumlah transistor, tegangan, dll.
  • berapa banyak waktu yang dibutuhkan suatu algoritma untuk berjalan, sebagai fungsi dari ukuran input
  • berapa banyak ruang yang perlu dijalankan suatu algoritma, sebagai fungsi dari ukuran masukan

Contoh

Untuk contoh jabat tangan di atas, semua orang di ruangan menjabat tangan orang lain. Dalam contoh itu, #handshakes ∈ Ɵ(N²). Mengapa?

Mundur sedikit: jumlah jabat tangan persis n-pilih-2 atau N*(N-1)/2 (Setiap orang N menggoyangkan tangan N-1 orang lain, tetapi ini jumlah jabat tangan ganda sehingga dibagi dengan 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Namun, untuk sejumlah besar orang, istilah linier N dikerdilkan dan secara efektif berkontribusi 0 terhadap rasio (dalam bagan: pecahan kotak kosong pada kotak diagonal di atas total menjadi lebih kecil karena jumlah peserta menjadi lebih besar). Oleh karena itu perilaku penskalaan adalah order N², atau jumlah jabat tangan "tumbuh seperti N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

Seolah-olah kotak kosong pada diagonal grafik (N * (N-1) / 2 tanda centang) tidak ada di sana (N2 tanda centang asimtotik).

(penyimpangan sementara dari "plain English" :) Jika Anda ingin membuktikan ini untuk diri sendiri, Anda bisa melakukan beberapa aljabar sederhana pada rasio untuk membaginya menjadi beberapa istilah (limberarti "dipertimbangkan dalam batas", abaikan saja jika Anda belum melihatnya, itu hanya notasi untuk "dan N benar-benar sangat besar"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Jumlah jabat tangan 'terlihat seperti' x² begitu banyak untuk nilai besar, bahwa jika kita menuliskan rasio # jabat tangan / x², fakta bahwa kita tidak perlu persis x² jabat tangan bahkan tidak akan muncul dalam desimal untuk sementara yang besar.

misalnya untuk x = 1 juta, rasio # jabat tangan / x²: 0,499999 ...


Membangun Intuisi

Ini memungkinkan kami membuat pernyataan seperti ...

"Untuk inputsize = cukup besar = N, tidak peduli apa faktor konstan, jika saya dua kali lipat ukuran input


362
2017-07-08 04:46



EDIT: Catatan cepat, ini hampir pasti membingungkan Notasi O besar (yang merupakan batas atas) dengan notasi Theta (yang merupakan batas atas dan bawah). Dalam pengalaman saya, ini sebenarnya khas diskusi dalam pengaturan non-akademik. Permintaan maaf untuk kebingungan apa pun yang disebabkan.

Dalam satu kalimat: Karena ukuran pekerjaan Anda bertambah, berapa lama lagi untuk menyelesaikannya?

Jelas itu hanya menggunakan "ukuran" sebagai input dan "waktu yang diambil" sebagai output - ide yang sama berlaku jika Anda ingin berbicara tentang penggunaan memori dll.

Berikut ini contoh di mana kami memiliki kaos N yang ingin kami keringkan. Baik menganggap itu sangat cepat untuk mendapatkan mereka dalam posisi pengeringan (yaitu interaksi manusia dapat diabaikan). Itu tidak terjadi dalam kehidupan nyata, tentu saja ...

  • Menggunakan garis cuci di luar: dengan asumsi Anda memiliki halaman belakang yang jauh tanpa batas, pencucian kering dalam waktu O (1). Betapapun banyaknya yang Anda miliki, matahari akan mendapat sinar matahari dan udara segar, sehingga ukurannya tidak mempengaruhi waktu pengeringan.

  • Menggunakan mesin pengering: Anda memasukkan 10 kaos dalam setiap beban, dan kemudian mereka selesai satu jam kemudian. (Abaikan angka yang sebenarnya di sini - mereka tidak relevan.) Jadi pengeringan 50 kemeja dibutuhkan tentang 5 kali selama pengeringan 10 baju.

  • Menempatkan segala sesuatu di lemari: Jika kita meletakkan semuanya dalam satu tumpukan besar dan membiarkan kehangatan umum melakukannya, akan membutuhkan waktu yang lama bagi kaos tengah untuk mengering. Saya tidak ingin menebak detailnya, tapi saya menduga ini setidaknya O (N ^ 2) - saat Anda meningkatkan beban pencucian, waktu pengeringan meningkat lebih cepat.

Satu aspek penting dari notasi "O besar" adalah itu tidak katakanlah algoritma mana yang akan lebih cepat untuk ukuran tertentu. Ambil hashtable (string kunci, nilai integer) vs array dari pasangan (string, integer). Apakah lebih cepat untuk menemukan kunci dalam hashtable atau elemen dalam array, berdasarkan string? (Yaitu untuk array, "temukan elemen pertama di mana bagian string cocok dengan kunci yang diberikan.") Hashtables umumnya diamortisasi (~ = "rata-rata") O (1) - setelah mereka mengatur, itu harus mengambil sekitar saat yang sama untuk menemukan entri dalam tabel 100 entri seperti dalam tabel entri 1.000.000. Menemukan elemen dalam array (berdasarkan konten daripada indeks) adalah linear, yaitu O (N) - rata-rata, Anda harus melihat setengah entri.

Apakah ini membuat hashtable lebih cepat daripada array untuk pencarian? Belum tentu. Jika Anda memiliki koleksi entri yang sangat kecil, array mungkin lebih cepat - Anda mungkin dapat memeriksa semua string dalam waktu yang diperlukan untuk hanya menghitung hashcode dari yang Anda lihat. Karena kumpulan data bertambah besar, bagaimanapun, hashtable akhirnya akan mengalahkan array.


237
2018-01-28 11:16



Big O menggambarkan batas atas pada perilaku pertumbuhan dari suatu fungsi, misalnya runtime suatu program, ketika input menjadi besar.

Contoh:

  • O (n): Jika saya menggandakan ukuran input, frekuensi runtime

  • Di2): Jika ukuran masukan menggandakan kuadrat runtime

  • O (log n): Jika ukuran input menggandakan waktu proses meningkat sebesar satu

  • O (2n): Jika ukuran input bertambah satu, frekuensi run-time

Ukuran input biasanya ruang dalam bit yang dibutuhkan untuk mewakili input.


120
2018-01-28 11:23



Notasi O besar paling sering digunakan oleh pemrogram sebagai ukuran perkiraan tentang berapa lama komputasi (algoritme) akan selesai diekspresikan sebagai fungsi dari ukuran set input.

Big O berguna untuk membandingkan seberapa baik dua algoritma akan bertambah seiring dengan bertambahnya jumlah input.

Lebih tepatnya Notasi O besar digunakan untuk mengekspresikan perilaku asymptotic dari suatu fungsi. Itu berarti bagaimana fungsi berperilaku ketika mendekati infinity.

Dalam banyak kasus, "O" dari suatu algoritma akan jatuh ke salah satu kasus berikut:

  • O (1) - Waktu untuk menyelesaikan adalah sama terlepas dari ukuran set input. Contohnya adalah mengakses elemen array berdasarkan indeks.
  • O (Log N) - Waktu untuk menyelesaikan meningkat kira-kira sesuai dengan log2 (n). Misalnya, 1024 item mengambil kira-kira dua kali selama 32 item, karena Log2 (1024) = 10 dan Log2 (32) = 5. Contohnya adalah menemukan item dalam pohon pencarian biner (BST).
  • DI) - Waktu untuk menyelesaikan skala tersebut secara linier dengan ukuran set input. Dengan kata lain jika Anda menggandakan jumlah item dalam set input, algoritma ini membutuhkan waktu sekitar dua kali lebih lama. Contohnya adalah menghitung jumlah item dalam daftar tertaut.
  • O (N Log N) - Waktu untuk menyelesaikan meningkat dengan jumlah item kali hasil Log2 (N). Contoh dari ini adalah semacam tumpukan dan semacam cepat.
  • O (N ^ 2) - Waktu untuk menyelesaikan kira-kira sama dengan kuadrat jumlah item. Contoh dari ini adalah semacam gelembung.
  • DI!) - Waktu untuk menyelesaikan adalah faktorial dari set input. Contoh dari ini adalah bepergian masalah solusi brute-force salesman.

Big O mengabaikan faktor-faktor yang tidak berkontribusi dalam cara yang berarti bagi kurva pertumbuhan fungsi ketika ukuran input meningkat menuju tak terhingga. Ini berarti bahwa konstanta yang ditambahkan atau dikalikan dengan fungsi tersebut diabaikan begitu saja.


97
2017-09-05 16:31



Big O adalah cara untuk "Ekspresikan" diri Anda dengan cara yang umum, "Berapa lama waktu / ruang yang diperlukan untuk menjalankan kode saya?".

Anda mungkin sering melihat O (n), O (n2), O (nlogn) dan seterusnya, semua ini hanyalah cara untuk menunjukkan; Bagaimana suatu algoritma berubah?

O (n) berarti Big O adalah n, dan sekarang Anda mungkin berpikir, "Apa itu n!" "N" adalah jumlah elemen. Imaging Anda ingin mencari Item dalam Array. Anda harus melihat pada Setiap elemen dan sebagai "Apakah Anda elemen / item yang benar?" dalam kasus terburuk, item berada pada indeks terakhir, yang berarti butuh waktu sebanyak item dalam daftar, sehingga menjadi generik, kami mengatakan "oh hey, n adalah jumlah nilai yang adil!" .

Jadi Anda mungkin mengerti apa "n2"Berarti, tetapi untuk menjadi lebih spesifik, bermainlah dengan pikiran Anda memiliki algoritma penggabungan yang sederhana dan paling sederhana; gelembungort. Algoritme ini perlu melihat seluruh daftar, untuk setiap item.

Daftarku

  1. 1
  2. 6
  3. 3

Aliran di sini akan menjadi:

  • Bandingkan 1 dan 6, mana yang terbesar? Ok 6 berada di posisi yang tepat, bergerak maju!
  • Bandingkan 6 dan 3, oh, 3 lebih sedikit! Mari kita pindahkan itu, Ok daftarnya berubah, kita harus mulai dari awal sekarang!

Ini adalah O n2 karena, Anda perlu melihat semua item dalam daftar ada item "n". Untuk setiap item, Anda melihat semua item sekali lagi, untuk membandingkan, ini juga "n", jadi untuk setiap item, Anda melihat "n" kali yang berarti n * n = n2

Saya harap ini sesederhana yang Anda inginkan.

Tapi ingat, Big O hanyalah cara untuk mengeksploitasi diri sendiri dalam cara ruang dan waktu.


77
2018-01-28 11:14



Big O menggambarkan sifat scaling mendasar dari suatu algoritma.

Ada banyak informasi yang Big O tidak memberi tahu Anda tentang suatu algoritma yang diberikan. Itu memotong ke tulang dan hanya memberikan informasi tentang sifat skala dari suatu algoritma, khususnya bagaimana penggunaan sumber daya (berpikir waktu atau memori) dari skala algoritma dalam menanggapi "ukuran input".

Pertimbangkan perbedaan antara mesin uap dan roket. Mereka tidak hanya varietas yang berbeda dari hal yang sama (seperti, katakanlah, mesin Prius vs mesin Lamborghini) tetapi mereka secara dramatis berbeda jenis sistem propulsi, pada intinya. Mesin uap mungkin lebih cepat daripada roket mainan, tetapi tidak ada mesin piston uap yang akan mampu mencapai kecepatan kendaraan peluncuran orbital. Ini karena sistem ini memiliki karakteristik penskalaan yang berbeda berkaitan dengan relasi bahan bakar yang diperlukan ("penggunaan sumber daya") untuk mencapai kecepatan tertentu ("ukuran masukan").

Mengapa ini sangat penting? Karena perangkat lunak berkaitan dengan masalah yang mungkin berbeda ukurannya dengan faktor hingga satu triliun. Pertimbangkan itu sebentar. Rasio antara kecepatan yang diperlukan untuk bepergian ke Bulan dan kecepatan berjalan manusia kurang dari 10.000: 1, dan itu benar-benar kecil dibandingkan dengan kisaran dalam perangkat lunak ukuran masukan yang mungkin dihadapi. Dan karena perangkat lunak mungkin menghadapi rentang astronomi dalam ukuran masukan, ada potensi kompleksitas Big O dari suatu algoritma, sifat dasar penskalaannya, untuk mengalahkan setiap detail penerapan.

Pertimbangkan contoh penyortiran kanonik. Bubble-sort adalah O (n2) saat merge-sort adalah O (n log n). Katakanlah Anda memiliki dua aplikasi penyortiran, aplikasi A yang menggunakan gelembung-sortir dan aplikasi B yang menggunakan gabungan-sort, dan katakanlah untuk ukuran masukan sekitar 30 elemen aplikasi A 1.000 kali lebih cepat daripada aplikasi B di penyortiran. Jika Anda tidak perlu memilah lebih dari 30 elemen maka jelas bahwa Anda sebaiknya memilih aplikasi A, karena jauh lebih cepat pada ukuran masukan ini. Namun, jika Anda menemukan bahwa Anda mungkin harus mengurutkan sepuluh juta item maka apa yang Anda harapkan adalah bahwa aplikasi B benar-benar berakhir menjadi ribuan kali lebih cepat daripada aplikasi A dalam hal ini, sepenuhnya karena cara masing-masing skala algoritma.


52
2018-01-28 13:12



Berikut adalah buku bestsary Inggris yang biasa saya gunakan ketika menjelaskan varietas umum Big-O

Dalam semua kasus, lebih suka algoritma yang lebih tinggi pada daftar untuk yang lebih rendah pada daftar. Namun, biaya pindah ke kelas kompleksitas yang lebih mahal bervariasi secara signifikan.

O (1):

Tidak tumbuh. Terlepas dari seberapa besar masalahnya, Anda dapat menyelesaikannya dalam jumlah waktu yang sama. Ini agak analog dengan penyiaran di mana dibutuhkan jumlah energi yang sama untuk disiarkan pada jarak tertentu, terlepas dari jumlah orang yang berada dalam jangkauan siaran.

O (log n):

Kerumitan ini sama dengan O (1) kecuali itu hanya sedikit lebih buruk. Untuk semua tujuan praktis, Anda dapat menganggap ini sebagai skala konstan yang sangat besar. Perbedaan dalam pekerjaan antara memproses 1 ribu dan 1 miliar item hanya merupakan faktor enam.

HAI(n):

Biaya pemecahan masalah sebanding dengan ukuran masalah. Jika masalah Anda berlipat ganda, maka biaya solusi menjadi dua kali lipat. Karena sebagian besar masalah harus dipindai ke dalam komputer dengan cara tertentu, seperti entri data, pembacaan disk, atau lalu lintas jaringan, ini umumnya merupakan faktor skala yang terjangkau.

HAI(n log n):

Kerumitan ini sangat mirip dengan HAI(n). Untuk semua tujuan praktis, keduanya setara. Tingkat kerumitan ini pada umumnya masih dianggap terukur. Dengan mengutak-atik beberapa asumsi HAI(n log n) algoritma dapat diubah menjadi HAI(n) algoritma. Misalnya, membatasi ukuran tombol mengurangi pengurutan HAI(n log n) untuk HAI(n).

HAI(n2):

Tumbuh seperti persegi, di mana n adalah panjang sisi persegi. Ini adalah tingkat pertumbuhan yang sama dengan "efek jaringan", di mana setiap orang dalam jaringan mungkin mengenal orang lain di jaringan. Pertumbuhan itu mahal. Sebagian besar solusi skalabel tidak dapat menggunakan algoritma dengan tingkat kerumitan ini tanpa melakukan senam yang signifikan. Ini umumnya berlaku untuk semua kompleksitas polinomial lainnya - HAI(nk) - demikian juga.

O (2n):

Tidak skala. Anda tidak memiliki harapan untuk memecahkan masalah ukuran yang tidak sepele. Berguna untuk mengetahui apa yang harus dihindari, dan bagi para ahli untuk menemukan algoritma perkiraan yang masuk HAI(nk).


35
2018-01-27 23:09



Big O adalah ukuran berapa banyak waktu / ruang yang digunakan algoritma relatif terhadap ukuran inputnya.

Jika suatu algoritma adalah O (n) maka waktu / ruang akan meningkat pada tingkat yang sama dengan inputnya.

Jika suatu algoritma adalah O (n2) maka peningkatan waktu / ruang pada tingkat inputnya dikuadratkan.

dan seterusnya.


34
2018-01-28 11:19



Sangat sulit untuk mengukur kecepatan program perangkat lunak, dan ketika kami mencoba, jawabannya bisa sangat rumit dan dipenuhi dengan pengecualian dan kasus-kasus khusus. Ini adalah masalah besar, karena semua pengecualian dan kasus khusus itu mengganggu dan tidak membantu ketika kita ingin membandingkan dua program yang berbeda dengan satu sama lain untuk mencari tahu mana yang "tercepat".

Sebagai hasil dari semua kompleksitas yang tidak membantu ini, orang-orang mencoba untuk menggambarkan kecepatan program perangkat lunak menggunakan ekspresi yang paling kecil dan paling kompleks (matematis) mungkin. Ekspresi ini sangat kasar perkiraan: Meskipun, dengan sedikit keberuntungan, mereka akan menangkap "esensi" apakah sepotong perangkat lunak cepat atau lambat.

Karena mereka adalah perkiraan, kami menggunakan huruf "O" (Big Oh) dalam ekspresi, sebagai konvensi untuk memberi sinyal kepada pembaca bahwa kami membuat penyederhanaan yang terlalu kasar. (Dan untuk memastikan bahwa tak seorang pun secara keliru berpikir bahwa ungkapan itu dengan cara apa pun akurat).

Jika Anda membaca "Oh" sebagai arti "pada urutan" atau "kira-kira" Anda tidak akan terlalu jauh salah. (Saya pikir pilihan Big-Oh mungkin merupakan upaya humor).

Satu-satunya hal yang coba dilakukan oleh "Big-Oh" ini adalah untuk mendeskripsikan seberapa banyak perangkat lunak itu melambat ketika kita meningkatkan jumlah data yang harus diproses oleh perangkat lunak. Jika kita menggandakan jumlah data yang perlu diproses, apakah perangkat lunak membutuhkan dua kali lebih lama untuk menyelesaikan kerjanya? Sepuluh kali lebih lama? Dalam praktiknya, ada sejumlah ekspresi besar-Oh yang sangat terbatas yang akan Anda hadapi dan perlu dikhawatirkan:

Yang baik:

  • O(1)  Konstan: Program mengambil waktu yang sama untuk menjalankan tidak peduli seberapa besar inputnya.
  • O(log n)  Logaritma: Program run-time hanya meningkat secara perlahan, bahkan dengan peningkatan besar dalam ukuran input.

Keburukan:

  • O(n)  Linear: Program run-time meningkat secara proporsional dengan ukuran input.
  • O(n^k)  Polinomial: - Waktu pemrosesan tumbuh lebih cepat dan lebih cepat - sebagai fungsi polinom - seiring dengan meningkatnya input.

... dan yang jelek:

  • O(k^n)  Eksponensial Program run-time meningkat sangat cepat dengan peningkatan moderat dalam ukuran masalah - itu hanya praktis untuk memproses set data kecil dengan algoritma eksponensial.
  • O(n!)  Faktorial Program run-time akan lebih lama daripada Anda mampu menunggu apa pun kecuali dataset yang sangat kecil dan paling sepele.

30
2018-05-29 13:51