Saya lebih suka definisi formal sesedikit mungkin dan matematika sederhana.

Catatan singkat, ini hampir pasti membingungkan notasi Big O (yang merupakan batas atas) dengan notasi Theta "Θ" (yang merupakan ikatan dua sisi). Dalam pengalaman saya, ini sebenarnya tipikal diskusi di lingkungan non-akademik. Permintaan maaf untuk kebingungan yang disebabkan.

Kompleksitas Big O dapat divisualisasikan dengan grafik ini:

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

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

Ada beberapa kata 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 dengan 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 bermakna;
• representasi: Big-O (dalam bentuknya yang paling sederhana) mengurangi perbandingan antara algoritma dengan satu variabel. Variabel itu dipilih berdasarkan pengamatan atau asumsi. Misalnya, algoritma pengurutan biasanya dibandingkan berdasarkan operasi perbandingan (membandingkan dua node untuk menentukan urutan relatifnya). Ini mengasumsikan bahwa perbandingan itu mahal. Tetapi bagaimana jika perbandingannya murah tetapi bertukar mahal? Itu mengubah perbandingan; dan
• kompleksitas: jika saya membutuhkan waktu satu detik untuk mengurutkan 10.000 elemen, berapa lama saya akan mengurutkan satu juta? Kompleksitas dalam hal ini adalah ukuran relatif untuk sesuatu yang lain.

Kembali dan baca kembali di atas ketika Anda sudah membaca sisanya.

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

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

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

Penambahan adalah yang paling sederhana. Anda membariskan angka-angka ke atas (ke kanan) dan menambahkan angka di kolom menulis angka 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. Cukup beralasan bahwa untuk menambahkan dua angka ini bersama-sama kita harus menambahkan bersama 6 digit (dan mungkin membawa angka 7). Jika kita menambahkan dua angka 100 digit bersamaan, kita harus melakukan 100 penambahan. Jika kita menambahkan dua angka 10.000 digit kita harus melakukan 10.000 penambahan.

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

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

Perkalian berbeda. Anda berbaris angka-angka, mengambil angka pertama di angka bawah dan mengalikannya dengan masing-masing angka di angka atas dan seterusnya melalui setiap digit. Jadi untuk melipatgandakan dua angka 6 digit kita harus melakukan 36 perkalian. Kita mungkin perlu melakukan sebanyak 10 atau 11 kolom tambahan untuk mendapatkan hasil akhir juga.

Jika kita memiliki dua angka 100 digit, kita perlu melakukan 10.000 perkalian dan 200 penambahan. Untuk dua angka satu juta digit kita perlu melakukan satu triliun (10 ¹² ) perkalian dan dua juta tambah.

Algoritme berskala dengan n- kuadrat , ini adalah O (n ² ) atau kompleksitas kuadratik . Ini adalah saat yang tepat untuk memperkenalkan konsep penting lainnya:

Kami hanya peduli pada bagian kompleksitas yang paling signifikan.

Cerdik mungkin menyadari bahwa kita dapat menyatakan jumlah operasi sebagai: n ² + 2n. Tetapi seperti yang Anda lihat dari contoh kami dengan dua angka satu juta digit masing-masing, suku kedua (2n) menjadi tidak signifikan (akuntansi untuk 0,0002% dari total operasi pada tahap itu).

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

Buku Telepon

Contoh terbaik berikutnya yang dapat saya pikirkan adalah buku telepon, biasanya disebut White Pages atau serupa tetapi bervariasi dari satu negara ke negara. Tetapi saya berbicara tentang orang 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 "John Smith" di buku telepon yang berisi 1.000.000 nama, apa yang akan Anda lakukan? Mengabaikan fakta bahwa Anda dapat menebak seberapa jauh S dimulai (anggap saja Anda tidak bisa), apa yang akan Anda lakukan?

Implementasi mungkin khas untuk membuka ke tengah, mengambil 500.000 ^th dan bandingkan dengan "Smith". Jika kebetulan "Smith, John", kami benar-benar beruntung. Jauh lebih mungkin bahwa "John Smith" akan ada sebelum atau sesudah nama itu. Jika setelah kita kemudian membagi setengah dari buku telepon menjadi dua dan ulangi. Jika sebelum maka kita membagi setengah dari buku telepon menjadi dua dan ulangi. Dan seterusnya.

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

Jadi, jika Anda ingin menemukan nama dalam buku telepon sejuta nama, Anda sebenarnya dapat menemukan nama dengan melakukan ini paling banyak 20 kali. Dalam membandingkan algoritma pencarian, kami memutuskan bahwa perbandingan ini adalah 'n' kami.

• Untuk buku telepon dengan 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 adalah O (log n) atau kompleksitas logaritmik . Sekarang logaritma yang dimaksud dapat berupa ln (basis e), log ₁₀ , log ₂ atau basis lainnya. Tidak masalah itu masih O (log n) seperti O (2n ² ) dan O (100n ² ) masih keduanya O (n ² ).

Ada baiknya pada saat ini untuk menjelaskan bahwa Big O dapat digunakan untuk menentukan tiga kasus dengan algoritma:

• Kasus Terbaik: Dalam pencarian buku telepon, kasus terbaik adalah bahwa kami menemukan nama dalam satu perbandingan. Ini adalah O (1) atau kompleksitas konstan ;
• Kasus yang diharapkan: Seperti yang 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 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 mencari nomor di buku telepon biasa. Bagaimana?

Anda mulai dengan nama depan dan membandingkan nomornya. Jika itu cocok, bagus, jika tidak, Anda beralih ke yang berikutnya. Anda harus melakukannya dengan cara ini karena buku teleponnya tidak berurutan (berdasarkan nomor telepon).

Jadi untuk menemukan nama yang diberikan nomor telepon (reverse lookup):

• Kasus Terbaik: O (1);
• Kasus yang diharapkan: O (n) (untuk 500.000); dan
• Kasus Terburuk: O (n) (untuk 1.000.000).

Salesman Bepergian

Ini adalah masalah yang cukup terkenal dalam ilmu komputer dan layak disebutkan. Dalam masalah ini, Anda memiliki N kota. Masing-masing kota itu terhubung dengan 1 atau lebih kota-kota lain dengan jalan dari 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 yang kurang dari itu karena beberapa di antaranya setara (A → B → C dan C → B → A sama, misalnya, karena mereka menggunakan jalan yang sama, hanya secara terbalik).

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 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 × 10 ⁶⁴

Jadi Big-O dari masalah Salesman Perjalanan adalah O (n!) 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

Poin lain yang ingin saya sebutkan adalah bahwa setiap algoritma yang memiliki kompleksitas O (n ^a ) dikatakan memiliki kompleksitas polinomial atau dapat dipecahkan dalam waktu polinomial .

O (n), O (n ² ) dll. Semuanya adalah waktu polinomial. Beberapa masalah tidak dapat diselesaikan dalam waktu polinomial. Hal-hal tertentu digunakan di dunia karena ini. Kriptografi Kunci Publik adalah contoh utama. Secara komputasi sulit untuk menemukan dua faktor utama dari jumlah yang sangat besar. Jika tidak, kami tidak dapat menggunakan sistem kunci publik yang kami gunakan.

Ngomong-ngomong, itu saja untuk penjelasan saya (semoga bahasa Inggris) Big O (direvisi).

Ini menunjukkan bagaimana suatu algoritma skala berdasarkan pada ukuran input.

O (n ² ) : dikenal sebagai kompleksitas Quadratic

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

Perhatikan bahwa jumlah item meningkat dengan faktor 10, tetapi waktu meningkat dengan faktor 10 ² . Pada dasarnya, n = 10 dan O (n ² ) memberi kita faktor penskalaan n ² yaitu 10 ² .

O (n) : dikenal sebagai kompleksitas Linear

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

Kali ini jumlah item meningkat dengan faktor 10, dan begitu pula waktu. n = 10 dan jadi faktor penskalaan O (n) adalah 10.

O (1) : dikenal dengan kompleksitas Konstan

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

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

O (log n) : dikenal sebagai kompleksitas Logaritmik

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

Jumlah perhitungan hanya bertambah satu log dari nilai input. Jadi dalam hal ini, dengan asumsi setiap perhitungan membutuhkan 1 detik, log dari input nadalah waktu yang diperlukan, karenanya log n.

Itulah intinya. Mereka mengurangi matematika sehingga mungkin bukan n ² atau apa pun yang mereka katakan, tetapi itu akan menjadi faktor yang mendominasi dalam penskalaan.

Notasi O-besar (juga disebut notasi "pertumbuhan asimptotik") adalah fungsi "terlihat" ketika Anda mengabaikan faktor dan hal-hal konstan di dekat titik asal . Kami menggunakannya untuk membicarakan bagaimana skala hal .

Dasar-dasar

untuk "cukup" input besar ...

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

notasi big-O tidak peduli tentang faktor konstan: fungsinya 9x²dikatakan "tumbuh persis seperti" 10x². Notasi big-O asimptotik tidak peduli tentang hal - hal non-asimptotik ("barang dekat asal" atau "apa yang terjadi ketika ukuran masalahnya kecil"): fungsinya 10x²dikatakan "tumbuh persis seperti" 10x² - x + 2.

Mengapa Anda ingin mengabaikan bagian persamaan yang lebih kecil? Karena mereka menjadi benar-benar dikerdilkan oleh sebagian besar 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 rasio saat Anda pergi ke tak terbatas. 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. Saat itulah kita mengatakan ...

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

... ini berarti bahwa untuk ukuran masalah "cukup besar" N (jika kita mengabaikan hal-hal di dekat titik asal), terdapat beberapa konstanta (mis. 2.5, yang sepenuhnya dibuat-buat) 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 non-terbesar (lihat bagian Faktor Konstan untuk alasan mengapa mereka biasanya tidak penting). Anda juga dapat menganggap persamaan di atas sebagai ikatan, dengan mengatakan, " Dalam skenario terburuk, waktu yang diperlukan tidak akan pernah lebih buruk daripada secara kasar N*log(N), dalam faktor 2,5 (faktor konstan yang tidak terlalu kita pedulikan) " .

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

Aplikasi

Sebagai konstruksi matematika murni, notasi O besar tidak terbatas pada berbicara tentang waktu dan memori pemrosesan. Anda dapat menggunakannya untuk membahas asimtotik apa pun di mana penskalaan bermakna, seperti:

• jumlah kemungkinan jabat tangan di antara Norang - orang di sebuah pesta ( Ɵ(N²), khususnya N(N-1)/2, tetapi yang penting adalah bahwa itu "bersisik" N²)
• jumlah orang yang mungkin melihat pemasaran viral sebagai fungsi waktu
• bagaimana latensi situs web skala dengan jumlah unit pemrosesan dalam CPU atau GPU atau cluster komputer
• bagaimana skala keluaran panas pada CPU mati sebagai fungsi dari jumlah transistor, tegangan, dll.
• berapa banyak waktu yang harus dijalankan oleh suatu algoritma, sebagai fungsi dari ukuran input
• berapa banyak ruang yang perlu dijalankan oleh algoritma, sebagai fungsi dari ukuran input

Contoh

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

Cadangkan sedikit: jumlah jabat tangan persis n-pilih-2 atau N*(N-1)/2(masing-masing N orang berjabat tangan N-1 orang lain, tetapi jabat tangan hitungan ganda ini begitu dibagi 2):

Namun, untuk jumlah orang yang sangat besar, istilah linier Ndikerdilkan dan secara efektif berkontribusi 0 terhadap rasio (dalam bagan: fraksi kotak kosong pada diagonal di atas kotak 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 di diagonal grafik (N * (N-1) / 2 tanda centang) bahkan tidak ada di sana (N ² menandai tanpa tanda asimtotik).

(penyimpangan sementara dari "Bahasa Inggris biasa" :) Jika Anda ingin membuktikan ini pada diri Anda sendiri, Anda dapat 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 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 'sepertinya' x² sangat banyak untuk nilai besar, sehingga jika kita menuliskan rasio # jabat tangan / x², fakta bahwa kita tidak membutuhkan jabat tangan x² persis bahkan tidak akan muncul dalam desimal untuk sementara waktu yang besar.

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

Membangun Intuisi

Ini memungkinkan kami membuat pernyataan seperti ...

"Untuk ukuran input cukup besar = N, tidak peduli apa faktor konstannya, jika saya gandakan ukuran input ...

• ... Saya gandakan waktu yang dibutuhkan algoritma O (N) ("linear time"). "

  N → (2N) = 2 ( N )

• ... Saya menggandakan kuadrat (quadruple) waktu yang dibutuhkan algoritma O (N²) ("kuadrat"). " (Mis. Masalah 100x lebih besar membutuhkan 100² = 10000x selama ... mungkin tidak berkelanjutan)

  N² → (2N) ² = 4 ( N² )

• ... Saya melakukan double-cubed (octuple) waktu yang dibutuhkan algoritma O (N³) ("cubic time"). " (Misalnya masalah 100x lebih besar membutuhkan 100³ = 1000000x selama ... sangat tidak berkelanjutan)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... Saya menambahkan jumlah tetap ke waktu yang dibutuhkan algoritma O (log (N)) ("waktu logaritmik"). " (Murah!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (jumlah tetap) + ( c log (N) )

• ... Saya tidak mengubah waktu yang dibutuhkan algoritma O (1) ("waktu konstan"). " (Termurah!)

  c * 1 → c * 1

• ... Saya "(pada dasarnya) menggandakan" waktu yang dibutuhkan algoritma O (N log (N)) " (cukup umum)

  kurang dari O (N ^1.000001 ), yang mungkin Anda anggap linier

• ... Saya secara konyol meningkatkan waktu yang dibutuhkan algoritma O (2 ^N ) ("waktu eksponensial"). " (Anda akan menggandakan (atau melipatgandakan, dll.) Waktu hanya dengan meningkatkan masalah dengan satu unit)

  2 ^N → 2 ^2N = (4 ^N ) ............ dengan kata lain ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[untuk yang cenderung matematis, Anda dapat mengarahkan mouse ke spoiler untuk sidenote kecil]

(dengan kredit ke https://stackoverflow.com/a/487292/711085 )

(secara teknis faktor konstan mungkin penting dalam beberapa contoh esoteris, tapi saya telah mengutarakan hal-hal di atas (misalnya dalam log (N)) sehingga tidak ada)

Ini adalah urutan pertumbuhan pertumbuhan yang diprogram oleh para pemrogram dan ilmuwan komputer terapan sebagai titik referensi. Mereka melihat ini sepanjang waktu. (Jadi, sementara Anda secara teknis dapat berpikir "Menggandakan input membuat algoritma O (√N) 1,414 kali lebih lambat," lebih baik untuk menganggapnya sebagai "ini lebih buruk daripada logaritmik tetapi lebih baik daripada linear".)

Faktor konstan

Biasanya, kami tidak peduli apa faktor konstan tertentu, karena mereka tidak mempengaruhi cara fungsi tumbuh. Misalnya, dua algoritma mungkin membutuhkan O(N)waktu untuk diselesaikan, tetapi satu mungkin dua kali lebih lambat dari yang lain. Kami biasanya tidak terlalu peduli kecuali faktornya sangat besar karena pengoptimalan adalah bisnis yang rumit ( Kapan pengoptimalan terlalu dini? ); juga tindakan semata-mata memilih algoritma dengan big-O yang lebih baik akan sering meningkatkan kinerja dengan urutan besarnya.

Beberapa algoritma yang asimptotik unggul (misalnya jenis non-perbandingan O(N log(log(N)))) dapat memiliki faktor konstan yang sangat besar (misalnya 100000*N log(log(N))), atau overhead yang relatif besar seperti O(N log(log(N)))dengan tersembunyi + 100*N, sehingga jarang digunakan bahkan pada "data besar".

Mengapa O (N) kadang-kadang adalah yang terbaik yang dapat Anda lakukan, yaitu mengapa kita membutuhkan struktur data

O(N)algoritma dalam beberapa hal adalah algoritma "terbaik" jika Anda perlu membaca semua data Anda. The Tindakan membaca sekelompok data adalah O(N)operasi. Memuatnya ke dalam memori biasanya O(N)(atau lebih cepat jika Anda memiliki dukungan perangkat keras, atau tidak ada waktu sama sekali jika Anda sudah membaca data). Namun, jika Anda menyentuh atau bahkan melihat setiap bagian data (atau bahkan setiap bagian data), algoritme Anda akan membutuhkan O(N)waktu untuk melakukan pencarian ini. Tidak peduli berapa lama algoritma Anda yang sebenarnya, itu akan setidaknya O(N)karena menghabiskan waktu melihat semua data.

Hal yang sama dapat dikatakan untuk tindakan penulisan . Semua algoritma yang mencetak N hal akan memakan waktu N karena output setidaknya selama itu (misalnya mencetak semua permutasi (cara untuk mengatur ulang) satu set kartu bermain N adalah faktorial:) O(N!).

Ini memotivasi penggunaan struktur data : struktur data membutuhkan membaca data hanya sekali (biasanya O(N)waktu), ditambah beberapa jumlah sewenang-wenang preprocessing (misalnya O(N)atau O(N log(N))atau O(N²)) yang kami mencoba untuk menjaga kecil. Setelah itu, memodifikasi struktur data (penyisipan / penghapusan / dll.) Dan membuat pertanyaan pada data membutuhkan waktu yang sangat sedikit, seperti O(1)atau O(log(N)). Anda kemudian melanjutkan untuk membuat sejumlah besar pertanyaan! Secara umum, semakin banyak pekerjaan yang ingin Anda lakukan sebelumnya, semakin sedikit pekerjaan yang harus Anda lakukan nanti.

Misalnya, Anda memiliki koordinat lintang dan bujur jutaan ruas jalan dan ingin menemukan semua persimpangan jalan.

• Metode naif: Jika Anda memiliki koordinat persimpangan jalan, dan ingin memeriksa jalan-jalan terdekat, Anda harus melalui jutaan segmen setiap kali, dan memeriksa masing-masing untuk kedekatan.
• Jika Anda hanya perlu melakukan ini satu kali, tidak akan menjadi masalah jika Anda harus melakukan metode naif O(N)hanya sekali, tetapi jika Anda ingin melakukannya berkali-kali (dalam hal ini, Nwaktu, satu kali untuk setiap segmen), kami O(N²)Harus melakukan pekerjaan, atau 1000000² = operasi 1000000000000. Tidak bagus (komputer modern dapat melakukan sekitar satu miliar operasi per detik).
• Jika kita menggunakan struktur sederhana yang disebut tabel hash (tabel pencarian kecepatan instan, juga dikenal sebagai hashmap atau kamus), kita membayar biaya yang kecil dengan memroses ulang semuanya O(N)tepat waktu. Setelah itu, hanya dibutuhkan waktu konstan rata-rata untuk mencari sesuatu dengan kuncinya (dalam hal ini, kunci kami adalah koordinat lintang dan bujur, dibulatkan menjadi kisi-kisi; kami mencari kisi-kisi yang berdekatan yang hanya ada 9, yang merupakan konstan).
• Tugas kami berubah dari tidak layak O(N²)menjadi mudah dikelola O(N), dan yang harus kami lakukan hanyalah membayar sedikit biaya untuk membuat tabel hash.
• analogi : Analogi dalam kasus khusus ini adalah teka-teki gambar: Kami menciptakan struktur data yang mengeksploitasi beberapa properti data. Jika segmen jalan kami seperti potongan puzzle, kami mengelompokkannya dengan warna dan pola yang serasi. Kami kemudian mengeksploitasi ini untuk menghindari melakukan pekerjaan ekstra nanti (membandingkan potongan-potongan puzzle seperti warna satu sama lain, bukan untuk setiap potongan puzzle lainnya).

Moral cerita: struktur data memungkinkan kita mempercepat operasi. Terlebih lagi, struktur data tingkat lanjut dapat membuat Anda menggabungkan, menunda, atau bahkan mengabaikan operasi dengan cara yang sangat pintar. Masalah yang berbeda akan memiliki analogi yang berbeda, tetapi mereka semua melibatkan pengorganisasian data dengan cara yang mengeksploitasi beberapa struktur yang kita pedulikan, atau yang telah kita paksakan untuk pembukuan. Kami bekerja lebih dulu (pada dasarnya merencanakan dan mengatur), dan sekarang tugas yang diulang jauh lebih mudah!

Contoh praktis: memvisualisasikan perintah pertumbuhan saat pengkodean

Notasi asimptotik, pada intinya, cukup terpisah dari pemrograman. Notasi asimptotik adalah kerangka matematika untuk berpikir tentang bagaimana hal-hal skala dan dapat digunakan di berbagai bidang. Yang mengatakan ... ini adalah bagaimana Anda menerapkan notasi asimptotik ke pengkodean.

Dasar-dasar: Setiap kali kita berinteraksi dengan setiap elemen dalam kumpulan ukuran A (seperti array, set, semua kunci peta, dll.), Atau melakukan iterasi loop, itu adalah faktor multiplikasi ukuran A Mengapa saya mengatakan "faktor multiplikatif"? - karena loop dan fungsi (hampir secara definisi) memiliki waktu berjalan multiplikatif: jumlah iterasi, waktu kerja yang dilakukan dalam loop (atau untuk fungsi: berapa kali Anda memanggil fungsi, waktu kerja dilakukan dalam fungsi). (Ini berlaku jika kita tidak melakukan sesuatu yang mewah, seperti melewatkan loop atau keluar dari loop lebih awal, atau mengubah aliran kontrol dalam fungsi berdasarkan argumen, yang sangat umum.) Berikut adalah beberapa contoh teknik visualisasi, dengan pseudocode yang menyertainya.

(di sini, xs mewakili unit kerja waktu konstan, instruksi prosesor, opcode interpreter, apa pun)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Contoh 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Contoh 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Jika kami melakukan sesuatu yang sedikit rumit, Anda mungkin masih dapat membayangkan secara visual apa yang terjadi:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Di sini, garis terkecil yang dapat dikenali yang dapat Anda gambar adalah yang penting; segitiga adalah bentuk dua dimensi (0,5 A ^ 2), seperti halnya persegi adalah bentuk dua dimensi (A ^ 2); faktor konstan dua di sini tetap dalam rasio asimptotik antara keduanya, namun, kami mengabaikannya seperti semua faktor ... (Ada beberapa nuansa yang disayangkan untuk teknik ini yang tidak saya masuki di sini; itu dapat menyesatkan Anda.)

Tentu saja ini tidak berarti bahwa loop dan fungsinya buruk; sebaliknya, mereka adalah blok bangunan bahasa pemrograman modern, dan kami menyukainya. Namun, kita dapat melihat bahwa cara kita menenun loop dan fungsi serta persyaratan bersama dengan data kita (aliran kontrol, dll.) Meniru waktu dan ruang penggunaan program kita! Jika penggunaan waktu dan ruang menjadi masalah, saat itulah kita menggunakan kepintaran dan menemukan algoritma atau struktur data yang mudah yang tidak kita pertimbangkan, untuk mengurangi urutan pertumbuhan. Namun demikian, teknik visualisasi ini (meskipun tidak selalu berhasil) dapat memberi Anda tebakan naif pada waktu berjalan terburuk.

Inilah hal lain yang bisa kita kenali secara visual:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Kami hanya dapat mengatur ulang ini dan melihatnya O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Atau mungkin Anda melakukan log (N) lintasan data, untuk O (N * log (N)) total waktu:

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Tidak ada hubungannya tetapi perlu disebutkan lagi: Jika kita melakukan hash (misalnya kamus / pencarian hashtable), itu adalah faktor O (1). Itu cukup cepat.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Jika kita melakukan sesuatu yang sangat rumit, seperti dengan fungsi rekursif atau algoritma divide-and-menaklukkan, Anda dapat menggunakan Teorema Master (biasanya bekerja), atau dalam kasus konyol Teorema Akra-Bazzi (hampir selalu berfungsi) Anda mencari menjalankan waktu algoritme Anda di Wikipedia.

Tetapi, programmer tidak berpikir seperti ini karena pada akhirnya, algoritma intuisi hanya menjadi kebiasaan. Anda akan mulai membuat kode sesuatu yang tidak efisien dan segera berpikir "apakah saya melakukan sesuatu yang sangat tidak efisien? ". Jika jawabannya "ya" DAN Anda memperkirakan itu benar-benar penting, maka Anda dapat mengambil langkah mundur dan memikirkan berbagai trik untuk membuat segalanya berjalan lebih cepat (jawabannya hampir selalu "menggunakan hashtable", jarang "gunakan pohon", dan sangat jarang sesuatu yang sedikit lebih rumit).

Kompleksitas kasus rata-rata diamortisasi dan

Ada juga konsep "amortisasi" dan / atau "kasus rata-rata" (perhatikan bahwa ini berbeda).

Kasus Rata-rata : Ini tidak lebih dari menggunakan notasi O besar untuk nilai yang diharapkan dari suatu fungsi, bukan fungsi itu sendiri. Dalam kasus biasa di mana Anda menganggap semua input memiliki kemungkinan yang sama, rerata kasus hanyalah rata-rata waktu berjalan. Misalnya dengan quicksort, meskipun kasus terburuk adalah O(N^2)untuk beberapa input yang benar-benar buruk, kasus rata-rata adalah biasa O(N log(N))(input yang benar-benar buruk jumlahnya sangat sedikit, sehingga sedikit yang kami tidak perhatikan dalam kasus rata-rata).

Amortized Worst-Case : Beberapa struktur data mungkin memiliki kompleksitas terburuk yang besar, tetapi menjamin bahwa jika Anda melakukan banyak dari operasi ini, jumlah rata-rata pekerjaan yang Anda lakukan akan lebih baik daripada yang terburuk. Misalnya, Anda mungkin memiliki struktur data yang biasanya membutuhkan O(1)waktu konstan . Namun, kadang-kadang akan 'cegukan' dan membutuhkan O(N)waktu untuk satu operasi acak, karena mungkin perlu melakukan beberapa pembukuan atau pengumpulan sampah atau sesuatu ... tetapi menjanjikan Anda bahwa jika itu cegukan, itu tidak akan cegukan lagi untuk N lebih banyak operasi. Biaya kasus terburuk masih O(N)per operasi, tetapi biaya diamortisasi selama banyak berjalan adalahO(N)/N =O(1)per operasi. Karena operasi besar cukup langka, sejumlah besar pekerjaan sesekali dapat dianggap berbaur dengan sisa pekerjaan sebagai faktor konstan. Kami mengatakan karya itu "diamortisasi" karena sejumlah besar panggilan yang hilang secara asimptotik.

Analogi untuk analisis diamortisasi:

Anda mengendarai mobil. Kadang-kadang, Anda perlu menghabiskan 10 menit pergi ke pompa bensin dan kemudian menghabiskan 1 menit mengisi tangki dengan gas. Jika Anda melakukan ini setiap kali Anda pergi ke mana pun dengan mobil Anda (menghabiskan 10 menit berkendara ke pompa bensin, menghabiskan beberapa detik mengisi sebagian kecil dari satu galon), itu akan sangat tidak efisien. Tetapi jika Anda mengisi tangki sekali setiap beberapa hari, 11 menit yang dihabiskan dengan mengemudi ke pompa bensin "diamortisasi" karena jumlah perjalanan yang cukup besar, sehingga Anda dapat mengabaikannya dan berpura-pura bahwa semua perjalanan Anda mungkin 5% lebih lama.

Perbandingan antara kasus rata-rata dan kasus terburuk diamortisasi:

• Kasus rata-rata: Kami membuat beberapa asumsi tentang input kami; yaitu jika input kita memiliki probabilitas yang berbeda, maka output / runtime kita akan memiliki probabilitas yang berbeda (yang kita ambil rata-rata). Biasanya, kami berasumsi bahwa input kami semuanya sama-sama berpeluang (probabilitas seragam), tetapi jika input dunia nyata tidak sesuai dengan asumsi kami tentang "input rata-rata", perhitungan output / runtime rata-rata mungkin tidak berarti. Jika Anda mengantisipasi input acak yang seragam, ini berguna untuk dipikirkan!
• Kasus terburuk diamortisasi: Jika Anda menggunakan struktur data kasus terburuk diamortisasi, kinerjanya dijamin berada dalam kasus terburuk diamortisasi ... akhirnya (bahkan jika input dipilih oleh iblis jahat yang tahu segalanya dan berusaha untuk mengacaukanmu). Biasanya, kami menggunakan ini untuk menganalisis algoritma yang mungkin sangat 'berombak' dalam kinerja dengan cegukan besar yang tidak terduga, tetapi seiring waktu berjalan dengan baik seperti halnya algoritma lainnya. (Namun, kecuali jika struktur data Anda memiliki batas atas untuk pekerjaan luar biasa yang ingin ditunda, penyerang jahat mungkin bisa memaksa Anda untuk mengejar jumlah maksimum pekerjaan yang ditunda sekaligus.

Padahal, jika Anda cukup khawatir tentang penyerang, ada banyak vektor serangan algoritmik lain yang perlu dikhawatirkan selain amortisasi dan huruf besar-kecil.)

Baik case rata-rata maupun amortisasi adalah alat yang sangat berguna untuk memikirkan dan merancang dengan mempertimbangkan skala.

(Lihat Perbedaan antara kasus rata-rata dan analisis diamortisasi jika tertarik dengan subtopik ini.)

Multidimensional big-O

Sebagian besar waktu, orang tidak menyadari bahwa ada lebih dari satu variabel yang bekerja. Sebagai contoh, dalam algoritma pencarian string, algoritma Anda mungkin membutuhkan waktu O([length of text] + [length of query]), yaitu linear dalam dua variabel seperti O(N+M). Algoritma lain yang lebih naif mungkin O([length of text]*[length of query])atau O(N*M). Mengabaikan banyak variabel adalah salah satu kekeliruan paling umum yang saya lihat dalam analisis algoritma, dan dapat menghambat Anda ketika merancang suatu algoritma.

Keseluruhan cerita

Perlu diingat bahwa big-O bukanlah keseluruhan cerita. Anda dapat secara drastis mempercepat beberapa algoritme dengan menggunakan caching, membuatnya tidak menyadari cache, menghindari kemacetan dengan bekerja dengan RAM alih-alih disk, menggunakan paralelisasi, atau melakukan pekerjaan sebelumnya - teknik-teknik ini seringkali tidak tergantung pada urutan pertumbuhan Notasi "big-O", meskipun Anda akan sering melihat jumlah core dalam notasi big-O dari algoritma paralel.

Juga perlu diingat bahwa karena kendala tersembunyi dari program Anda, Anda mungkin tidak benar-benar peduli tentang perilaku asimptotik. Anda mungkin bekerja dengan jumlah nilai terbatas, misalnya:

• Jika Anda mengurutkan sekitar 5 elemen, Anda tidak ingin menggunakan O(N log(N))quicksort cepat ; Anda ingin menggunakan jenis penyisipan, yang berfungsi baik pada input kecil. Situasi ini sering muncul dalam algoritma divide-and-conquer, di mana Anda membagi masalah menjadi subproblem yang lebih kecil dan lebih kecil, seperti pengurutan rekursif, transformasi Fourier cepat, atau perkalian matriks.
• Jika beberapa nilai dibatasi secara efektif karena beberapa fakta tersembunyi (mis. Rata-rata nama manusia dibatasi sekitar 40 huruf, dan usia manusia dibatasi sekitar 150). Anda juga dapat memberi batasan pada input Anda untuk secara efektif membuat ketentuan konstan.

Dalam praktiknya, bahkan di antara algoritma yang memiliki kinerja asimptotik yang sama atau serupa, manfaat relatifnya sebenarnya dapat didorong oleh hal-hal lain, seperti: faktor kinerja lainnya (quicksort dan mergesort keduanya O(N log(N)), tetapi quicksort memanfaatkan cache CPU); pertimbangan non-kinerja, seperti kemudahan implementasi; apakah perpustakaan tersedia, dan bagaimana reputasi dan pemeliharaan perpustakaan itu.

Program juga akan berjalan lebih lambat di komputer 500MHz vs komputer 2GHz. Kami tidak benar-benar menganggap ini sebagai bagian dari batasan sumber daya, karena kami memikirkan penskalaan dalam hal sumber daya mesin (misalnya per siklus jam), bukan per detik nyata. Namun, ada hal serupa yang dapat 'diam-diam' memengaruhi kinerja, seperti apakah Anda menjalankan emulasi, atau apakah kompilator mengoptimalkan kode atau tidak. Ini mungkin membuat beberapa operasi dasar memakan waktu lebih lama (bahkan relatif satu sama lain), atau bahkan mempercepat atau memperlambat beberapa operasi tanpa gejala (bahkan relatif satu sama lain). Efeknya mungkin kecil atau besar antara implementasi dan / atau lingkungan yang berbeda. Apakah Anda beralih bahasa atau mesin untuk menambah sedikit kerja ekstra itu? Itu tergantung pada seratus alasan lain (kebutuhan, keterampilan, rekan kerja, produktivitas programmer,

Masalah-masalah di atas, seperti efek dari pilihan bahasa pemrograman yang digunakan, hampir tidak pernah dianggap sebagai bagian dari faktor konstan (atau seharusnya); namun orang harus menyadarinya karena kadang-kadang (meskipun jarang) mereka dapat mempengaruhi hal-hal. Misalnya dalam cpython, implementasi antrian prioritas asli secara asimptot tidak optimal ( O(log(N))bukan O(1)untuk pilihan penyisipan atau pencarian-min); apakah Anda menggunakan implementasi lain? Mungkin tidak, karena implementasi C mungkin lebih cepat, dan mungkin ada masalah serupa lainnya di tempat lain. Ada pengorbanan; terkadang mereka penting dan terkadang tidak.

( edit : Penjelasan "Bahasa Inggris biasa" berakhir di sini.)

Tambahan matematika

Untuk kelengkapan, definisi yang tepat dari notasi O-besar adalah sebagai berikut: f(x) ∈ O(g(x))berarti bahwa "f secara asimptot dibatasi oleh const * g": mengabaikan segala sesuatu di bawah beberapa nilai x hingga, ada konstanta yang demikian |f(x)| ≤ const * |g(x)|. (Simbol lainnya adalah sebagai berikut: sama seperti Osarana ≤,Ω berarti ≥. Ada varian huruf kecil: oberarti <, dan ωberarti>.) f(x) ∈ Ɵ(g(x))Berarti keduanya f(x) ∈ O(g(x))dan f(x) ∈ Ω(g(x))(dibatasi oleh g): ada beberapa konstanta sehingga akan selalu terletak di "band" antara const1*g(x)dan const2*g(x). Ini adalah pernyataan asimptotik terkuat yang dapat Anda buat dan kira-kira setara dengan== . (Maaf, saya memilih untuk menunda penyebutan simbol nilai absolut sampai sekarang, demi kejelasan; terutama karena saya belum pernah melihat nilai-nilai negatif muncul dalam konteks ilmu komputer.)

Orang akan sering menggunakan = O(...), yang mungkin merupakan notasi 'comp-sci' yang lebih benar, dan sepenuhnya sah untuk digunakan; "f = O (...)" dibaca "f is order ... / f dibatasi oleh xxx ..." dan dianggap sebagai "f adalah ekspresi yang asimtotiknya adalah ...". Saya diajari menggunakan yang lebih keras ∈ O(...). ∈berarti "adalah elemen" (masih dibaca seperti sebelumnya). Dalam kasus khusus ini, O(N²)mengandung elemen-elemen seperti { 2 N²,3 N² , 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} dan jauh besar, tapi masih set.

O dan Ω tidak simetris (n = O (n²), tetapi n² bukan O (n)), tetapi Ɵ simetris, dan (karena semua hubungan ini bersifat transitif dan refleksif) Ɵ, oleh karena itu, simetris dan transitif dan refleksif , dan karenanya mempartisi himpunan semua fungsi ke dalam kelas kesetaraan . Kelas kesetaraan adalah serangkaian hal yang kami anggap sama. Dengan kata lain, mengingat fungsi apa pun yang dapat Anda pikirkan, Anda dapat menemukan 'perwakilan asimptotik' kanonik / unik dari kelas (dengan secara umum mengambil batasan ... saya pikir ); sama seperti Anda dapat mengelompokkan semua bilangan bulat ke dalam odds atau genap, Anda dapat mengelompokkan semua fungsi dengan Ɵ ke x-ish, log (x) ^ 2-ish, dll ... dengan dasarnya mengabaikan istilah yang lebih kecil (tapi kadang-kadang Anda mungkin terjebak dengan fungsi yang lebih rumit yang merupakan kelas yang terpisah untuk diri mereka sendiri).

The =notasi mungkin menjadi orang yang lebih umum dan bahkan digunakan dalam makalah oleh para ilmuwan komputer terkenal di dunia. Selain itu, sering terjadi bahwa dalam suasana kasual, orang akan mengatakan O(...)ketika mereka bermaksud Ɵ(...); ini benar secara teknis karena himpunan hal Ɵ(exactlyThis)adalah bagian dari O(noGreaterThanThis)... dan lebih mudah untuk mengetik. ;-)

EDIT: Catatan singkat, ini hampir pasti membingungkan notasi Big O (yang merupakan batas atas) dengan notasi Theta (yang merupakan batas atas dan bawah). Dalam pengalaman saya, ini sebenarnya tipikal diskusi di lingkungan non-akademik. Permintaan maaf untuk kebingungan yang disebabkan.

Dalam satu kalimat: Ketika ukuran pekerjaan Anda naik, 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 adalah contoh di mana kami memiliki kaus oblong yang ingin kami keringkan. Kami akan menganggap sangat cepat untuk membuatnya dalam posisi pengeringan (yaitu interaksi manusia dapat diabaikan). Bukan itu yang terjadi di kehidupan nyata, tentu saja ...

• Menggunakan garis pencucian di luar: dengan asumsi Anda memiliki halaman belakang yang sangat luas, pencucian mengering dalam waktu O (1). Sebanyak apa pun yang Anda miliki, itu akan mendapatkan matahari dan udara segar yang sama, sehingga ukurannya tidak mempengaruhi waktu pengeringan.

• Menggunakan mesin pengering: Anda menempatkan 10 baju di setiap beban, dan kemudian selesai satu jam kemudian. (Abaikan angka aktual di sini - mereka tidak relevan.) Jadi, mengeringkan 50 kaus membutuhkan waktu sekitar 5 kali selama pengeringan 10 kaus.

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

Salah satu aspek penting dari notasi "O besar" adalah bahwa ia tidak mengatakan algoritma mana yang akan lebih cepat untuk ukuran tertentu. Ambil hashtable (kunci string, nilai integer) vs array pasangan (string, integer). Apakah lebih cepat menemukan kunci di hashtable atau elemen dalam array, berdasarkan pada string? (Yaitu untuk larik, "temukan elemen pertama di mana bagian string cocok dengan kunci yang diberikan.") Hashtable pada umumnya diamortisasi (~ = "rata-rata") O (1) - begitu mereka diatur, itu harus memakan waktu sekitar saat yang sama untuk menemukan entri dalam tabel entri 100 seperti pada 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 hashtabel lebih cepat daripada array untuk pencarian? Belum tentu. Jika Anda memiliki koleksi entri yang sangat kecil, sebuah array mungkin lebih cepat - Anda mungkin dapat memeriksa semua string dalam waktu yang diperlukan untuk hanya menghitung kode hash dari yang Anda lihat. Ketika set data tumbuh lebih besar, namun, hashtable pada akhirnya akan mengalahkan array.

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

Contoh:

• O (n): Jika saya menggandakan ukuran input, runtime akan berlipat ganda

• O (n ² ): Jika ukuran input menggandakan runtime quadruple

• O (log n): Jika ukuran input dua kali lipat runtime bertambah satu

• O (2 ⁿ ): Jika ukuran input bertambah satu, runtime akan berlipat ganda

Ukuran input biasanya adalah ruang dalam bit yang dibutuhkan untuk merepresentasikan input.

Notasi O besar paling sering digunakan oleh programmer sebagai ukuran perkiraan berapa lama suatu komputasi (algoritma) akan selesai untuk diekspresikan sebagai fungsi dari ukuran set input.

Big O berguna untuk membandingkan seberapa baik dua algoritma akan meningkat seiring dengan meningkatnya jumlah input.

Lebih tepatnya notasi Big O digunakan untuk mengekspresikan perilaku asimptotik suatu fungsi. Itu berarti bagaimana fungsi berperilaku saat mendekati tak terhingga.

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

• O (1) - Waktu untuk menyelesaikan adalah sama terlepas dari ukuran input yang ditetapkan. Contohnya adalah mengakses elemen array dengan indeks.
• O (Log N) - Waktu untuk menyelesaikan peningkatan kira-kira sejalan dengan log2 (n). Misalnya 1024 item kira-kira dua kali lebih lama dari 32 item, karena Log2 (1024) = 10 dan Log2 (32) = 5. Contohnya adalah menemukan item dalam pohon pencarian biner (BST).
• O (N) - Waktu untuk menyelesaikan skala itu secara linear dengan ukuran set input. Dengan kata lain, jika Anda menggandakan jumlah item dalam set input, algoritme akan memakan waktu kira-kira dua kali lebih lama. Contohnya adalah menghitung jumlah item dalam daftar yang ditautkan.
• O (N Log N) - Waktu untuk menyelesaikan peningkatan dengan jumlah item dikalikan hasil Log2 (N). Contohnya adalah heap sort dan quick sort .
• O (N ^ 2) - Waktu untuk menyelesaikan kira-kira sama dengan kuadrat jumlah item. Contohnya adalah semacam gelembung .
• O (N!) - Waktu untuk menyelesaikan adalah faktorial dari set input. Contohnya adalah solusi brute force problem salesman keliling .

Big O mengabaikan faktor-faktor yang tidak berkontribusi dengan cara yang berarti pada kurva pertumbuhan fungsi karena ukuran input meningkat ke arah infinity. Ini berarti bahwa konstanta yang ditambahkan atau dikalikan dengan fungsi diabaikan begitu saja.

Big O hanyalah cara untuk "Mengekspresikan" diri Anda dengan cara yang umum, "Berapa banyak waktu / ruang yang diperlukan untuk menjalankan kode saya?".

Anda mungkin sering melihat O (n), O (n ² ), O (nlogn) dan sebagainya, semua ini hanyalah cara untuk ditampilkan; Bagaimana suatu algoritma berubah?

O (n) berarti Big O adalah n, dan sekarang Anda mungkin berpikir, "Apa itu n !?" Nah "n" adalah jumlah elemen. Pencitraan, Anda ingin mencari Item dalam Array. Anda harus melihat pada Setiap elemen dan sebagai "Apakah Anda elemen / item yang benar?" dalam kasus terburuk, item tersebut berada pada indeks terakhir, yang berarti bahwa diperlukan waktu sebanyak ada item dalam daftar, jadi untuk menjadi generik, kita mengatakan "oh hei, n adalah jumlah nilai yang diberikan adil!" .

Jadi Anda mungkin mengerti apa arti "n ² ", tetapi untuk lebih spesifik, bermainlah dengan pemikiran yang Anda miliki sederhana, yang paling sederhana dari algoritma pengurutan; Bubbleort. Algoritma ini perlu melihat seluruh daftar, untuk setiap item.

Daftarku

1. 1
2. 6
3. 3

Aliran di sini adalah:

• Bandingkan 1 dan 6, mana yang terbesar? Ok 6 ada di posisi yang tepat, bergerak maju!
• Bandingkan 6 dan 3, oh, 3 kurang! Mari kita lanjutkan, ok daftar berubah, kita harus mulai dari awal sekarang!

Ini adalah O n ² 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 artinya n * n = n ²

Saya harap ini sesederhana yang Anda inginkan.

Tapi ingat, Big O hanyalah cara untuk menunjukkan diri Anda dalam ruang dan waktu.

Big O menjelaskan sifat penskalaan mendasar dari suatu algoritma.

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

Pertimbangkan perbedaan antara mesin uap dan roket. Mereka bukan hanya varietas 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 dari roket mainan, tetapi tidak ada mesin piston uap yang dapat mencapai kecepatan kendaraan peluncuran orbital. Ini karena sistem ini memiliki karakteristik penskalaan yang berbeda sehubungan dengan hubungan bahan bakar yang diperlukan ("penggunaan sumber daya") untuk mencapai kecepatan tertentu ("ukuran input").

Mengapa ini sangat penting? Karena perangkat lunak menangani masalah yang mungkin berbeda ukurannya dengan faktor hingga satu triliun. Pertimbangkan itu sejenak. Rasio antara kecepatan yang diperlukan untuk melakukan perjalanan ke Bulan dan kecepatan berjalan manusia kurang dari 10.000: 1, dan itu benar-benar kecil dibandingkan dengan kisaran ukuran perangkat lunak input yang mungkin dihadapi. Dan karena perangkat lunak mungkin menghadapi kisaran astronomis dalam ukuran input, ada potensi kompleksitas Big O suatu algoritma, itu adalah sifat penskalaan fundamental, untuk melampaui detail implementasi.

Pertimbangkan contoh penyortiran kanonik. Bubble-sort adalah O (n ² ) sedangkan merge-sort adalah O (n log n). Katakanlah Anda memiliki dua aplikasi penyortiran, aplikasi A yang menggunakan bubble-sort dan aplikasi B yang menggunakan merge-sort, dan katakanlah untuk ukuran input sekitar 30 elemen aplikasi A adalah 1.000x lebih cepat daripada aplikasi B dalam penyortiran. Jika Anda tidak perlu menyortir lebih dari 30 elemen maka jelas bahwa Anda harus memilih aplikasi A, karena jauh lebih cepat pada ukuran input ini. Namun, jika Anda menemukan bahwa Anda mungkin harus mengurutkan sepuluh juta item maka yang Anda harapkan adalah aplikasi B sebenarnya berakhir ribuan kali lebih cepat daripada aplikasi A dalam hal ini, sepenuhnya karena cara masing-masing algoritma menskala.

Berikut adalah bestiary Inggris sederhana yang saya cenderung gunakan ketika menjelaskan varietas umum Big-O

Dalam semua kasus, lebih suka algoritma yang lebih tinggi pada daftar daripada 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 ):

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

O ( n ):

Biaya penyelesaian masalah sebanding dengan ukuran masalah. Jika masalah Anda berlipat ganda, maka biaya solusi berlipat ganda. Karena sebagian besar masalah harus dipindai ke komputer dalam beberapa cara, seperti entri data, disk membaca, atau lalu lintas jaringan, ini umumnya merupakan faktor penskalaan yang terjangkau.

O ( n log n ):

Kompleksitas ini sangat mirip dengan O ( n ) . Untuk semua tujuan praktis, keduanya setara. Tingkat kerumitan ini umumnya masih dianggap scalable. Dengan mengubah asumsi beberapa algoritma O ( n log n ) dapat diubah menjadi algoritma O ( n ) . Misalnya, membatasi ukuran kunci mengurangi penyortiran dari O ( n log n ) ke O ( n ) .

O ( n ² ):

Tumbuh sebagai bujur sangkar, di mana n adalah panjang sisi bujur sangkar. 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 yang dapat diskalakan tidak dapat menggunakan algoritme dengan tingkat kerumitan ini tanpa melakukan senam yang signifikan. Ini umumnya berlaku untuk semua kompleksitas polinomial lainnya - O ( n ^k ) - juga.

O (2 ⁿ ):

Tidak berskala. Anda tidak memiliki harapan untuk menyelesaikan masalah yang tidak sepele. Berguna untuk mengetahui apa yang harus dihindari, dan bagi para ahli untuk menemukan algoritma perkiraan yang berada di O ( n ^k ) .

Big O adalah ukuran seberapa banyak waktu / ruang yang digunakan suatu 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 (n ² ) maka waktu / ruang meningkat pada tingkat inputnya kuadrat.

dan seterusnya.

Apa penjelasan bahasa Inggris yang sederhana tentang Big O? Dengan definisi formal sesedikit mungkin dan matematika sederhana.

Penjelasan Bahasa Inggris Biasa tentang Kebutuhan Notasi O Besar:

Saat kami memprogram, kami mencoba menyelesaikan masalah. Apa yang kita kode disebut algoritma. Notasi O Besar memungkinkan kita untuk membandingkan kinerja kasus terburuk dari algoritma kami dengan cara standar. Spesifikasi perangkat keras bervariasi dari waktu ke waktu dan peningkatan perangkat keras dapat mengurangi waktu yang dibutuhkan untuk menjalankan algoritma. Tetapi mengganti perangkat keras tidak berarti algoritme kami lebih baik atau lebih baik seiring waktu, karena algoritme kami masih sama. Jadi untuk memungkinkan kami membandingkan algoritma yang berbeda, untuk menentukan apakah ada yang lebih baik atau tidak, kami menggunakan notasi O Besar.

Penjelasan Bahasa Inggris yang Biasa tentang What Big O Notation adalah:

Tidak semua algoritma berjalan dalam jumlah waktu yang sama, dan dapat bervariasi berdasarkan jumlah item dalam input, yang akan kita sebut n . Berdasarkan hal ini, kami mempertimbangkan analisis kasus yang lebih buruk, atau batas atas run-time karena n menjadi lebih besar dan lebih besar. Kita harus menyadari apa itu n , karena banyak notasi O Besar merujuknya.

Sangat sulit untuk mengukur kecepatan program perangkat lunak, dan ketika kami mencoba, jawabannya bisa sangat kompleks dan dipenuhi dengan pengecualian dan 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 satu sama lain untuk mengetahui mana yang "tercepat".

Sebagai hasil dari semua kerumitan yang tidak membantu ini, orang-orang mencoba untuk menggambarkan kecepatan program perangkat lunak menggunakan ekspresi (matematika) terkecil dan paling kompleks. Ungkapan-ungkapan ini adalah perkiraan yang sangat kasar: Meskipun, dengan sedikit keberuntungan, mereka akan menangkap "esensi" dari apakah suatu 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 berlebihan. (Dan untuk memastikan bahwa tidak ada yang salah berpikir bahwa ungkapan itu akurat).

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

Satu-satunya hal yang coba dilakukan oleh ekspresi "Besar-Oh" ini adalah untuk menggambarkan seberapa banyak perangkat lunak melambat saat kami meningkatkan jumlah data yang harus diproses oleh perangkat lunak. Jika kami menggandakan jumlah data yang perlu diproses, apakah perangkat lunak perlu dua kali lebih lama untuk menyelesaikannya? Sepuluh kali lebih lama? Dalam praktiknya, ada sejumlah besar ekspresi Oh besar yang akan Anda temui dan perlu khawatirkan:

Yang baik:

• O(1) Konstan : Program membutuhkan waktu yang sama untuk menjalankan tidak peduli seberapa besar inputnya.
• O(log n) Logaritmik : Waktu berjalan program hanya meningkat secara perlahan, bahkan dengan peningkatan besar dalam ukuran input.

Keburukan:

• O(n) Linear : Waktu berjalan program meningkat secara proporsional dengan ukuran input.
• O(n^k) Polinomial : - Waktu pemrosesan tumbuh lebih cepat dan lebih cepat - sebagai fungsi polinomial - saat ukuran input bertambah.

... dan yang jelek:

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

Jawaban sederhana yang mudah dapat:

Big O mewakili waktu / ruang terburuk untuk algoritma itu. Algoritma tidak akan pernah mengambil lebih banyak ruang / waktu di atas batas itu. Big O mewakili kompleksitas waktu / ruang dalam kasus ekstrem.

Oke, 2 sen saya.

Big-O, adalah tingkat peningkatan sumber daya yang dikonsumsi oleh program, wrt masalah-instance-size

Sumber Daya: Bisa jadi total-waktu CPU, bisa ruang RAM maksimum. Secara default mengacu pada waktu CPU.

Katakan masalahnya adalah "Temukan jumlahnya",

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance = {5,10,15} ==> masalah-instance-size = 3, iterations-in-loop = 3

problem-instance = {5,10,15,20,25} ==> masalah-instance-size = 5 iterasi-in-loop = 5

Untuk input ukuran "n", program tumbuh dengan kecepatan "n" iterasi dalam array. Karenanya Big-O adalah N yang dinyatakan sebagai O (n)

Katakan masalahnya adalah "Temukan Kombinasi",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance = {5,10,15} ==> masalah-instance-size = 3, total-iterations = 3 * 3 = 9

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations = 5 * 5 = 25

Untuk input ukuran "n", program ini tumbuh dengan kecepatan iterasi "n * n" dalam array. Karenanya Big-O adalah N ^{2 yang} dinyatakan sebagai O (n ² )

Notasi O besar adalah cara menggambarkan batas atas suatu algoritma dalam hal ruang atau waktu berjalan. N adalah jumlah elemen dalam masalah (yaitu ukuran array, jumlah node dalam pohon, dll.) Kami tertarik untuk menggambarkan waktu berjalan saat n menjadi besar.

Ketika kita mengatakan beberapa algoritma adalah O (f (n)) kita mengatakan bahwa waktu berjalan (atau ruang yang dibutuhkan) oleh algoritma itu selalu lebih rendah daripada beberapa kali konstan f (n).

Mengatakan bahwa pencarian biner memiliki waktu berjalan O (logn) adalah mengatakan bahwa ada beberapa c yang konstan yang dapat Anda gandakan log (n) dengan yang akan selalu lebih besar daripada waktu berjalan pencarian biner. Dalam hal ini Anda akan selalu memiliki beberapa faktor perbandingan log (n) yang konstan.

Dengan kata lain di mana g (n) adalah waktu berjalan dari algoritma Anda, kami mengatakan bahwa g (n) = O (f (n)) ketika g (n) <= c * f (n) ketika n> k, di mana c dan k adalah beberapa konstanta.

" Apa penjelasan bahasa Inggris yang sederhana tentang Big O? Dengan sesedikit mungkin definisi formal dan matematika sederhana. "

Pertanyaan yang sangat sederhana dan sederhana seperti itu tampaknya paling tidak layak mendapatkan jawaban yang sama pendeknya, seperti yang mungkin diterima seorang siswa saat les.

Notasi O besar hanya memberi tahu berapa banyak waktu * suatu algoritma dapat berjalan di dalam, dalam hal hanya jumlah data input **.

(* dalam arti yang indah, bebas waktu!)
(** yang penting, karena orang akan selalu menginginkan lebih , apakah mereka hidup hari ini atau besok)

Nah, apa yang hebat tentang notasi O Besar jika itu yang dilakukannya?

• Secara praktis, analisis Big O sangat berguna dan penting karena Big O menempatkan fokus pada kompleksitas algoritme itu sendiri dan sepenuhnya mengabaikan segala sesuatu yang hanya berupa konstanta proporsionalitas — seperti mesin JavaScript, kecepatan CPU, koneksi Internet Anda, dan semua hal-hal yang menjadi cepat menjadi sebagai laughably usang sebagai Model T . Big O berfokus pada kinerja hanya dengan cara yang sama pentingnya bagi orang yang hidup di masa sekarang atau di masa depan.

• Notasi O besar juga menyoroti secara langsung pada prinsip terpenting dari pemrograman / rekayasa komputer, fakta yang menginspirasi semua programmer yang baik untuk terus berpikir dan bermimpi: satu-satunya cara untuk mencapai hasil di luar lambatnya kemajuan teknologi adalah menciptakan yang lebih baik algoritma .

Contoh algoritme (Jawa):

// Given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Deskripsi algoritma:

• Algoritma ini mencari daftar, item per item, mencari kunci,

• Iterasi pada setiap item dalam daftar, jika kuncinya lalu kembali Benar,

• Jika loop selesai tanpa menemukan kunci, kembalikan False.

Notasi O besar mewakili batas atas pada Kompleksitas (Waktu, Ruang, ..)

Untuk menemukan The Big-O pada Kompleksitas Waktu:

• Hitung berapa banyak waktu (mengenai ukuran input) kasus terburuk:

• Kasus Terburuk: kuncinya tidak ada dalam daftar.

• Waktu (Kasus Terburuk) = 4n + 1

• Waktu: O (4n + 1) = O (n) | di Big-O, konstanta diabaikan

• O (n) ~ Linier

Ada juga Big-Omega, yang mewakili kerumitan Best-Case:

• Best-Case: kuncinya adalah item pertama.

• Waktu (Best-Case) = 4

• Waktu: Ω (4) = O (1) ~ Instan \ Konstan

O Besar

f (x) = O ( g (x)) ketika x pergi ke a (misalnya, a = + ∞) berarti ada fungsi k sedemikian rupa sehingga:

1. f (x) = k (x) g (x)

2. k dibatasi di beberapa lingkungan a (jika a = + ∞, ini berarti bahwa ada angka N dan M sehingga untuk setiap x> N, | k (x) | <M).

Dengan kata lain, dalam bahasa Inggris sederhana: f (x) = O ( g (x)), x → a, berarti bahwa dalam lingkungan a, f terurai menjadi produk dari g dan beberapa fungsi terikat.

Kecil o

Omong-omong, di sini adalah untuk perbandingan definisi dari o kecil.

f (x) = o ( g (x)) ketika x pergi ke sarana yang ada fungsi k sehingga:

1. f (x) = k (x) g (x)

2. k (x) pergi ke 0 ketika x pergi ke a.

Contohnya

• sin x = O (x) ketika x → 0.

• sin x = O (1) saat x → + ∞,

• x ² + x = O (x) ketika x → 0,

• x ² + x = O (x ² ) ketika x → + ∞,

• ln (x) = o (x) = O (x) ketika x → + ∞.

Perhatian! Notasi dengan tanda sama dengan "=" menggunakan "kesetaraan palsu": benar bahwa o (g (x)) = O (g (x)), tetapi salah bahwa O (g (x)) = o (g (x)). Demikian pula, tidak apa-apa untuk menulis "ln (x) = o (x) ketika x → + ∞", tetapi rumus "o (x) = ln (x)" tidak masuk akal.

Lebih banyak contoh

• O (1) = O (n) = O (n ² ) ketika n → + ∞ (tetapi tidak sebaliknya, persamaannya adalah "palsu"),

• O (n) + O (n ² ) = O (n ² ) saat n → + ∞

• O (O (n ² )) = O (n ² ) saat n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ) saat n → + ∞

Ini artikel Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

Notasi O besar adalah cara menggambarkan seberapa cepat suatu algoritma akan berjalan mengingat jumlah parameter input yang berubah-ubah, yang kita sebut "n". Ini berguna dalam ilmu komputer karena mesin yang berbeda beroperasi pada kecepatan yang berbeda, dan hanya mengatakan bahwa algoritma membutuhkan waktu 5 detik tidak banyak memberi tahu Anda karena saat Anda menjalankan sistem dengan prosesor octo-core 4,5 Ghz, saya mungkin sedang menjalankan sebuah sistem 800 Mhz berusia 15 tahun, yang bisa memakan waktu lebih lama terlepas dari algoritme. Jadi alih-alih menentukan seberapa cepat suatu algoritma berjalan dalam hal waktu, kami mengatakan seberapa cepat itu berjalan dalam hal jumlah parameter input, atau "n". Dengan menjelaskan algoritma dengan cara ini, kami dapat membandingkan kecepatan algoritma tanpa harus memperhitungkan kecepatan komputer itu sendiri.

Tidak yakin saya berkontribusi lebih jauh pada subjek tetapi masih berpikir saya akan berbagi: Saya pernah menemukan posting blog ini memiliki beberapa penjelasan & contoh yang cukup membantu (meskipun sangat mendasar) di Big O:

Melalui contoh-contoh, ini membantu memasukkan dasar-dasar telanjang ke tengkorak saya yang seperti kulit penyu, jadi saya pikir ini adalah 10 menit yang cukup turun untuk membuat Anda menuju ke arah yang benar.

Anda ingin tahu semua yang perlu diketahui tentang O besar? Saya juga.

Jadi untuk membicarakan O besar, saya akan menggunakan kata-kata yang hanya memiliki satu ketukan di dalamnya. Satu suara per kata. Kata-kata kecil cepat. Anda tahu kata-kata ini, dan saya juga. Kami akan menggunakan kata-kata dengan satu suara. Mereka kecil. Saya yakin Anda akan tahu semua kata yang akan kami gunakan!

Sekarang, mari kita bicara tentang pekerjaan. Sebagian besar waktu, saya tidak suka bekerja. Apakah kamu suka bekerja? Mungkin itu yang Anda lakukan, tetapi saya yakin tidak.

Saya tidak suka pergi kerja. Saya tidak suka menghabiskan waktu di tempat kerja. Jika saya memiliki cara saya, saya hanya ingin bermain, dan melakukan hal-hal yang menyenangkan. Apakah Anda merasakan hal yang sama seperti saya?

Sekarang kadang-kadang, saya harus pergi bekerja. Menyedihkan, tetapi benar. Jadi, ketika saya di tempat kerja, saya memiliki aturan: Saya mencoba melakukan lebih sedikit pekerjaan. Sedekat tidak ada pekerjaan yang saya bisa. Lalu aku pergi bermain!

Jadi, inilah berita besar: O besar dapat membantu saya untuk tidak melakukan pekerjaan! Saya bisa bermain lebih banyak waktu, jika saya tahu O besar. Kurang kerja, lebih banyak bermain! Itulah yang dilakukan O besar.

Sekarang saya punya pekerjaan. Saya memiliki daftar ini: satu, dua, tiga, empat, lima, enam. Saya harus menambahkan semua hal dalam daftar ini.

Wow, aku benci bekerja. Tetapi oh well, saya harus melakukan ini. Jadi di sini saya pergi.

Satu tambah dua adalah tiga ... ditambah tiga adalah enam ... dan empat adalah ... Saya tidak tahu. Saya tersesat. Terlalu sulit bagi saya untuk melakukannya di kepala saya. Saya tidak terlalu peduli dengan pekerjaan semacam ini.

Jadi jangan lakukan pekerjaan. Mari kita dan saya berpikir betapa sulitnya itu. Berapa banyak pekerjaan yang harus saya lakukan, untuk menambah enam angka?

Baiklah, mari kita lihat. Saya harus menambahkan satu dan dua, dan kemudian menambahkannya menjadi tiga, dan kemudian menambahkannya ke empat… Semua dalam semua, saya hitung enam tambah. Saya harus melakukan enam tambahan untuk menyelesaikan ini.

Ini dia O besar, untuk memberi tahu kami betapa sulitnya matematika ini.

Big O mengatakan: kita harus melakukan enam tambahan untuk menyelesaikan ini. Satu tambah, untuk setiap hal dari satu hingga enam. Enam bit kecil pekerjaan ... setiap bit pekerjaan adalah satu tambahan.

Yah, saya tidak akan melakukan pekerjaan untuk menambahkannya sekarang. Tapi saya tahu betapa sulitnya itu. Itu akan menjadi enam tambah.

Oh tidak, sekarang saya punya lebih banyak pekerjaan. Sheesh. Siapa yang membuat barang semacam ini ?!

Sekarang mereka meminta saya untuk menambah dari satu menjadi sepuluh! Mengapa saya melakukan itu? Saya tidak ingin menambahkan satu hingga enam. Untuk menambah dari satu menjadi sepuluh ... yah ... itu akan lebih sulit!

Seberapa sulitkah itu? Berapa banyak lagi pekerjaan yang harus saya lakukan? Apakah saya memerlukan lebih atau kurang langkah?

Yah, saya kira saya harus melakukan sepuluh menambahkan ... satu untuk setiap hal dari satu hingga sepuluh. Sepuluh lebih dari enam. Saya harus bekerja lebih banyak untuk menambah dari satu menjadi sepuluh, dari satu ke enam!

Saya tidak ingin menambahkan sekarang. Saya hanya ingin memikirkan betapa sulitnya menambahkan sebanyak itu. Dan, saya harap, bermain secepat mungkin.

Untuk menambah dari satu menjadi enam, itu adalah pekerjaan. Tetapi apakah Anda melihat, untuk menambah dari satu menjadi sepuluh, itu lebih banyak pekerjaan?

Big O adalah teman dan milikmu. Big O membantu kita berpikir tentang berapa banyak pekerjaan yang harus kita lakukan, sehingga kita dapat merencanakan. Dan, jika kita berteman dengan O besar, dia dapat membantu kita memilih pekerjaan yang tidak terlalu sulit!

Sekarang kita harus melakukan pekerjaan baru. Oh tidak. Saya tidak suka pekerjaan ini sama sekali.

Pekerjaan baru adalah: tambahkan semua hal dari satu ke n.

Tunggu! Apa itu n? Apakah saya melewatkan itu? Bagaimana saya bisa menambahkan dari satu ke n jika Anda tidak memberi tahu saya apa n?

Yah, aku tidak tahu apa itu. Saya tidak diberitahu. Apakah kamu? Tidak? Baiklah. Jadi kita tidak bisa melakukan pekerjaan. Wah.

Tetapi meskipun kita tidak akan melakukan pekerjaan sekarang, kita dapat menebak seberapa sulitnya, jika kita tahu n. Kita harus menjumlahkan n hal, kan? Tentu saja!

Sekarang, inilah O yang besar, dan dia akan memberi tahu kita betapa sulitnya pekerjaan ini. Dia mengatakan: menambahkan semua hal dari satu ke N, satu demi satu, adalah O (n). Untuk menambahkan semua hal ini, [Aku tahu aku harus menambahkan n kali.] [1] Itu adalah O besar! Dia memberi tahu kita betapa sulitnya melakukan beberapa jenis pekerjaan.

Bagi saya, saya menganggap O besar seperti bos yang besar, lamban. Dia berpikir tentang pekerjaan, tetapi dia tidak melakukannya. Dia mungkin berkata, "Pekerjaan itu cepat." Atau, dia mungkin berkata, "Pekerjaan itu sangat lambat dan sulit!" Tapi dia tidak melakukan pekerjaannya. Dia hanya melihat pekerjaannya, dan kemudian dia memberi tahu kita berapa banyak waktu yang diperlukan.

Saya sangat peduli untuk O besar. Mengapa? Saya tidak suka bekerja! Tidak ada yang suka bekerja. Itu sebabnya kita semua mencintai O besar! Dia memberi tahu kita seberapa cepat kita bisa bekerja. Dia membantu kita memikirkan betapa sulitnya bekerja.

Uh oh, lebih banyak pekerjaan. Sekarang, jangan lakukan pekerjaan. Tapi, mari kita buat rencana untuk melakukannya, langkah demi langkah.

Mereka memberi kami setumpuk sepuluh kartu. Mereka semua berbaur: tujuh, empat, dua, enam ... tidak lurus sama sekali. Dan sekarang ... tugas kita adalah menyortirnya.

Ergh. Kedengarannya seperti banyak pekerjaan!

Bagaimana kita bisa mengurutkan dek ini? Aku punya rencana.

Saya akan melihat setiap pasangan kartu, pasangan demi pasangan, melalui tumpukan kartu, dari awal hingga akhir. Jika kartu pertama dalam satu pasangan besar dan kartu berikutnya dalam pasangan itu kecil, saya menukar mereka. Lain, saya pergi ke pasangan berikutnya, dan seterusnya dan seterusnya ... dan segera, dek selesai.

Ketika dek selesai, saya bertanya: apakah saya menukar kartu di pass itu? Jika demikian, saya harus melakukannya sekali lagi, dari atas.

Pada titik tertentu, pada suatu waktu, tidak akan ada swap, dan jenis dek kami akan selesai. Begitu banyak pekerjaan!

Berapa banyak pekerjaan yang harus dilakukan untuk menyortir kartu dengan aturan-aturan itu?

Saya punya sepuluh kartu. Dan, sebagian besar waktu - yaitu, jika saya tidak memiliki banyak keberuntungan - saya harus melalui seluruh dek hingga sepuluh kali, dengan hingga sepuluh kartu bertukar setiap kali melalui dek.

Big O, bantu aku!

Big O masuk dan berkata: untuk setumpuk kartu n, mengurutkannya dengan cara ini akan dilakukan dalam waktu O (N kuadrat).

Kenapa dia bilang n kuadrat?

Nah, Anda tahu n kuadrat adalah n kali n. Sekarang, saya mengerti: kartu n diperiksa, hingga apa yang mungkin n kali melalui dek. Itu adalah dua loop, masing-masing dengan n langkah. Itu n kuadrat banyak pekerjaan yang harus dilakukan. Banyak pekerjaan, pasti!

Sekarang ketika O besar mengatakan akan mengambil O (n kuadrat) bekerja, dia tidak berarti n kuadrat menambahkan, di hidung. Mungkin sedikit lebih sedikit, untuk beberapa kasus. Tetapi dalam kasus terburuk, itu akan dekat dan langkah-langkah pekerjaan persegi untuk menyortir dek.

Sekarang di sinilah O besar adalah teman kita.

Big O menunjukkan ini: saat n menjadi besar, ketika kami mengurutkan kartu, pekerjaan itu JAUH LEBIH BANYAK KERAS daripada pekerjaan hanya menambahkan-hal-hal-baru ini. Bagaimana kita tahu ini?

Nah, jika n menjadi sangat besar, kita tidak peduli apa yang bisa kita tambahkan ke n atau n kuadrat.

Untuk n besar, n kuadrat lebih besar dari n.

Big O memberi tahu kita bahwa untuk menyortir sesuatu lebih sulit daripada menambahkan sesuatu. O (n kuadrat) lebih dari O (n) untuk besar n. Itu berarti: jika n menjadi sangat besar, untuk mengurutkan setumpuk campuran dari hal-hal HARUS membutuhkan lebih banyak waktu, daripada hanya menambahkan dan hal-hal campuran.

Big O tidak menyelesaikan pekerjaan untuk kita. Big O memberi tahu kita betapa sulitnya pekerjaan ini.

Saya memiliki setumpuk kartu. Saya memang menyortirnya. Kamu membantu. Terima kasih.

Apakah ada cara yang lebih cepat untuk menyortir kartu? Bisakah O besar membantu kami?

Ya, ada cara yang lebih cepat! Butuh waktu untuk belajar, tetapi berhasil ... dan bekerja cukup cepat. Anda dapat mencobanya juga, tetapi luangkan waktu Anda dengan setiap langkah dan jangan kehilangan tempat Anda.

Dengan cara baru ini untuk mengurutkan kartu, kami tidak memeriksa pasangan kartu seperti yang kami lakukan beberapa waktu lalu. Berikut adalah aturan baru Anda untuk mengurutkan dek ini:

Satu: Saya memilih satu kartu di bagian dek yang sedang kami kerjakan sekarang. Anda dapat memilih satu untuk saya jika Anda mau. (Pertama kali kita melakukan ini, “bagian dari geladak yang sedang kita kerjakan sekarang” adalah seluruh geladak, tentu saja.)

Dua: Saya merentangkan tumpukan kartu yang Anda pilih. Apa ini splay; bagaimana cara saya melebar? Baiklah, saya beralih dari kartu awal ke bawah, satu per satu, dan saya mencari kartu yang lebih tinggi daripada kartu splay.

Tiga: Saya naik dari kartu akhir ke atas, dan saya mencari kartu yang lebih rendah daripada kartu splay.

Setelah saya menemukan dua kartu ini, saya menukar mereka, dan terus mencari lebih banyak kartu untuk ditukar. Yaitu, saya kembali ke langkah Dua, dan melihat kartu yang Anda pilih lagi.

Pada titik tertentu, loop ini (dari Dua ke Tiga) akan berakhir. Itu berakhir ketika kedua bagian dari pencarian ini bertemu di kartu splay. Kemudian, kami baru saja memasang deck dengan kartu yang Anda pilih pada langkah Satu. Sekarang, semua kartu di dekat awal lebih rendah daripada kartu splay; dan kartu di dekat akhir lebih tinggi daripada kartu splay. Trik keren!

Empat (dan ini bagian yang menyenangkan): Saya punya dua deck kecil sekarang, satu lebih rendah dari kartu splay, dan satu lagi lebih tinggi. Sekarang saya pergi ke langkah satu, di setiap dek kecil! Artinya, saya mulai dari langkah pertama di dek kecil pertama, dan ketika pekerjaan itu selesai, saya mulai dari langkah pertama di dek kecil berikutnya.

Saya memecah deck menjadi beberapa bagian, dan mengurutkan setiap bagian, lebih kecil dan lebih kecil, dan pada suatu waktu saya tidak memiliki pekerjaan lagi. Sekarang ini mungkin tampak lambat, dengan semua aturan. Tapi percayalah, itu tidak lambat sama sekali. Ini jauh lebih sedikit bekerja daripada cara pertama untuk menyortir!

Disebut apa ini? Ini disebut Quick Sort! Semacam itu dibuat oleh seorang pria bernama CAR Hoare dan dia menyebutnya Quick Sort. Sekarang, Quick Sort terbiasa sepanjang waktu!

Sort Cepat memecah deck besar dalam yang kecil. Artinya, itu memecah tugas-tugas besar dalam yang kecil.

Hmmm. Mungkin ada aturan di sana, saya pikir. Untuk membuat tugas-tugas besar kecil, hancurkan.

Jenis ini cukup cepat. Seberapa cepat? Big O memberitahu kita: jenis ini membutuhkan O (n log n) pekerjaan yang harus dilakukan, dalam kasus yang berarti.

Apakah ini lebih cepat atau kurang dari jenis pertama? Big O, tolong bantu!

Jenis pertama adalah O (n kuadrat). Tetapi Sortir Cepat adalah O (n log n). Anda tahu bahwa n log n kurang dari n kuadrat, untuk n besar, kan? Nah, begitulah kita tahu bahwa Quick Sort cepat!

Jika Anda harus mengurutkan deck, apa cara terbaik? Nah, Anda dapat melakukan apa yang Anda inginkan, tetapi saya akan memilih Quick Sort.

Mengapa saya memilih Penyortiran Cepat? Saya tidak suka bekerja, tentu saja! Saya ingin pekerjaan dilakukan segera setelah saya bisa menyelesaikannya.

Bagaimana saya tahu Penyortiran Cepat kurang bekerja? Saya tahu bahwa O (n log n) kurang dari O (n kuadrat). O lebih kecil, jadi Sort Cepat kurang berfungsi!

Sekarang Anda kenal teman saya, O Besar. Dia membantu kami melakukan lebih sedikit pekerjaan. Dan jika Anda tahu O besar, Anda bisa melakukan lebih sedikit pekerjaan juga!

Anda belajar semua itu dengan saya! Kamu sangat cerdas! Terima kasih banyak!

Sekarang pekerjaan sudah selesai, ayo main!

[1]: Ada cara untuk menipu dan menambahkan semua hal dari satu ke n, semuanya sekaligus. Beberapa anak bernama Gauss mengetahui hal ini ketika dia berusia delapan tahun. Tapi aku tidak sepintar itu, jadi jangan tanya aku bagaimana dia melakukannya .

Saya memiliki cara yang lebih sederhana untuk memahami kompleksitas waktu. Metrik yang paling umum untuk menghitung kompleksitas waktu adalah notasi O Besar. Ini menghapus semua faktor konstan sehingga waktu berjalan dapat diperkirakan dalam kaitannya dengan N saat N mendekati tak terhingga. Secara umum Anda bisa memikirkannya seperti ini:

statement;

Konstan. Waktu berjalan pernyataan tidak akan berubah dalam kaitannya dengan N

for ( i = 0; i < N; i++ )
  statement;

Linier. Waktu berjalan dari loop berbanding lurus dengan N. Saat N berlipat ganda, demikian juga waktu berjalan.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

Apakah kuadratik. Waktu berjalan dari dua loop sebanding dengan kuadrat N. Ketika N berlipat ganda, waktu berjalan meningkat sebesar N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

Apakah logaritmik. Waktu berjalan dari algoritma sebanding dengan berapa kali N dapat dibagi dengan 2. Ini karena algoritma membagi area kerja menjadi dua dengan setiap iterasi.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Apakah N * log (N). Waktu berjalan terdiri dari N loop (iteratif atau rekursif) yang bersifat logaritmik, sehingga algoritma ini merupakan kombinasi linear dan logaritmik.

Secara umum, melakukan sesuatu dengan setiap item dalam satu dimensi adalah linier, melakukan sesuatu dengan setiap item dalam dua dimensi adalah kuadratik, dan membagi area kerja menjadi setengahnya adalah logaritmik. Ada ukuran Big O lainnya seperti kubik, eksponensial, dan akar kuadrat, tetapi mereka hampir tidak umum. Notasi O besar digambarkan sebagai O () di mana ukurannya. Algoritme quicksort akan digambarkan sebagai O (N * log (N)).

Catatan: Tidak satu pun dari ini telah memperhitungkan ukuran-ukuran kasus terbaik, rata-rata, dan terburuk. Masing-masing akan memiliki notasi Big O sendiri. Perhatikan juga bahwa ini adalah penjelasan yang SANGAT sederhana. Big O adalah yang paling umum, tetapi juga lebih kompleks yang saya tunjukkan. Ada juga notasi lain seperti omega besar, o kecil, dan theta besar. Anda mungkin tidak akan menjumpai mereka di luar kursus analisis algoritma.

• Lihat lebih lanjut di: Sini

Katakan Anda memesan Harry Potter: Selesaikan 8-Film Collection [Blu-ray] dari Amazon dan unduh koleksi film yang sama secara online pada saat bersamaan. Anda ingin menguji metode mana yang lebih cepat. Pengiriman hampir tiba satu hari dan unduhan selesai sekitar 30 menit sebelumnya. Bagus! Jadi ini balapan yang ketat.

Bagaimana jika saya memesan beberapa film Blu-ray seperti The Lord of the Rings, Twilight, The Dark Knight Trilogy, dll. Dan mengunduh semua film secara bersamaan? Kali ini, pengiriman masih perlu satu hari untuk selesai, tetapi pengunduhan online membutuhkan 3 hari untuk selesai. Untuk belanja online, jumlah barang yang dibeli (input) tidak mempengaruhi waktu pengiriman. Outputnya konstan. Kami menyebutnya O (1) .

Untuk pengunduhan online, waktu pengunduhan berbanding lurus dengan ukuran file film (input). Kami menyebutnya O (n) .

Dari percobaan, kita tahu bahwa belanja online lebih baik daripada pengunduhan online. Sangat penting untuk memahami notasi O besar karena ini membantu Anda untuk menganalisis skalabilitas dan efisiensi algoritma.

Catatan: Notasi O besar mewakili skenario terburuk dari suatu algoritma. Mari kita asumsikan bahwa O (1) dan O (n) adalah skenario terburuk dari contoh di atas.

Referensi : http://carlcheo.com/compsci

Asumsikan kita sedang berbicara tentang algoritma A , yang harus melakukan sesuatu dengan dataset ukuran n .

Kemudian O( <some expression X involving n> )berarti, dalam bahasa Inggris sederhana:

Jika Anda kurang beruntung saat menjalankan A, mungkin diperlukan sebanyak X (n) operasi untuk menyelesaikan.

Seperti yang terjadi, ada fungsi-fungsi tertentu (menganggap mereka sebagai implementasi dari X (n) ) yang cenderung terjadi cukup sering. Ini adalah terkenal dan mudah dibandingkan (Contoh: 1, Log N, N, N^2, N!, dll ..)

Dengan membandingkan ini ketika berbicara tentang A dan algoritma lainnya, mudah untuk peringkat algoritma sesuai dengan jumlah operasi mereka mungkin (kasus terburuk) yang harus diselesaikan.

Secara umum, tujuan kami adalah menemukan atau menyusun algoritma A sedemikian rupa sehingga akan memiliki fungsi X(n)yang mengembalikan angka serendah mungkin.

Jika Anda memiliki gagasan tak terbatas yang sesuai di kepala Anda, maka ada uraian yang sangat singkat:

Notasi O besar memberi tahu Anda biaya untuk menyelesaikan masalah yang sangat besar.

Dan selanjutnya

Faktor konstan dapat diabaikan

Jika Anda memutakhirkan ke komputer yang dapat menjalankan algoritme Anda dua kali lebih cepat, notasi O besar tidak akan menyadarinya. Perbaikan faktor konstan terlalu kecil bahkan untuk diperhatikan dalam skala yang bekerja dengan notasi O besar. Perhatikan bahwa ini adalah bagian yang disengaja dari desain notasi O besar.

Meskipun demikian, apa pun yang "lebih besar" dari faktor konstan dapat dideteksi.

Ketika tertarik melakukan perhitungan yang ukurannya "besar" cukup untuk dianggap kira-kira tak terbatas, maka notasi O besar adalah kira-kira biaya penyelesaian masalah Anda.

Jika hal di atas tidak masuk akal, maka Anda tidak memiliki gagasan intuitif tak terbatas yang kompatibel di kepala Anda, dan Anda mungkin harus mengabaikan semua hal di atas; satu-satunya cara saya tahu untuk membuat ide-ide ini ketat, atau menjelaskannya jika mereka belum berguna secara intuitif, adalah dengan pertama-tama mengajarkan Anda notasi O besar atau sesuatu yang serupa. (walaupun, begitu Anda memahami notasi O besar di masa depan, mungkin ada baiknya untuk meninjau kembali ide-ide ini)

Apa penjelasan bahasa Inggris sederhana dari notasi "O Besar"?

Catatan Sangat Cepat:

O dalam "Big O" mengacu pada "Orde" (atau tepatnya "orde")
sehingga Anda bisa mendapatkan idenya secara harfiah bahwa itu digunakan untuk memesan sesuatu untuk membandingkannya.

• "Big O" melakukan dua hal:

  1. Perkirakan berapa banyak langkah metode yang diterapkan komputer Anda untuk menyelesaikan suatu tugas.
  2. Fasilitasi proses untuk membandingkan dengan orang lain untuk menentukan apakah itu baik atau tidak?
  3. "Big O mencapai dua di atas dengan standar Notations.

• Ada tujuh notasi yang paling banyak digunakan

  1. O (1), berarti komputer Anda menyelesaikan tugas dengan 1langkah, sangat bagus, Memesan No.1
  2. O (logN), artinya komputer Anda menyelesaikan tugas dengan logNlangkah - langkah, bagusnya, Memerintahkan No.2
  3. O (N), selesaikan tugas dengan Nlangkah - langkah, wajar, Pesanan No. 3
  4. O (NlogN), akhiri tugas dengan O(NlogN)langkah - langkah, tidak baik, Pesan No.4
  5. O (N ^ 2), selesaikan tugas dengan N^2langkah - langkah, itu buruk, Pesanan No.5
  6. O (2 ^ N), selesaikan tugas dengan 2^Nlangkah - langkah, mengerikan, Pesan No. 6
  7. O (N!), Selesaikan tugas dengan N!langkah - langkah, mengerikan, Pesan No.7

Misalkan Anda mendapatkan notasi O(N^2), tidak hanya Anda jelas metode ini mengambil langkah-langkah N * N untuk menyelesaikan tugas, juga Anda melihat bahwa itu tidak baik O(NlogN)dari peringkatnya.

Harap perhatikan urutan di akhir baris, hanya untuk pengertian Anda yang lebih baik. Ada lebih dari 7 notasi jika semua kemungkinan dipertimbangkan.

Dalam CS, serangkaian langkah untuk menyelesaikan tugas disebut algoritma.
Dalam Terminologi, notasi Big O digunakan untuk menggambarkan kinerja atau kompleksitas suatu algoritma.

Selain itu, Big O menetapkan kasus terburuk atau mengukur langkah-langkah Batas Atas.
Anda bisa merujuk ke Big-Ω (Big-Omega) untuk case terbaik.

Notasi Big-Ω (Big-Omega) (artikel) | Akademi Khan

• Ringkasan
  "Big O" menggambarkan kinerja algoritma dan mengevaluasinya.

  atau mengatasinya secara formal, "Big O" mengklasifikasikan algoritma dan membakukan proses perbandingan.

Cara termudah untuk melihatnya (dalam bahasa Inggris)

Kami mencoba melihat bagaimana jumlah parameter input, mempengaruhi waktu berjalan suatu algoritma. Jika waktu berjalan aplikasi Anda sebanding dengan jumlah parameter input, maka dikatakan dalam Big O dari n.

Pernyataan di atas adalah awal yang baik tetapi tidak sepenuhnya benar.

Penjelasan yang lebih akurat (matematis)

Seharusnya

n = jumlah parameter input

T (n) = Fungsi aktual yang menyatakan waktu berjalan dari algoritma sebagai fungsi dari n

c = konstanta

f (n) = Fungsi perkiraan yang mengekspresikan waktu berjalan dari algoritma sebagai fungsi dari n

Maka sejauh menyangkut O Besar, perkiraan f (n) dianggap cukup baik selama kondisi di bawah ini benar.

lim     T(n) ≤ c×f(n)
n→∞

Persamaan ini dibaca ketika n mendekati tak terhingga, T n, kurang dari atau sama dengan c kali f dari n.

Dalam notasi O besar ini ditulis sebagai

T(n)∈O(n)

Ini dibaca sebagai T n adalah dalam O besar n.

Kembali ke Bahasa Inggris

Berdasarkan definisi matematika di atas, jika Anda mengatakan algoritma Anda adalah O Besar n, itu berarti fungsi n (jumlah parameter input) atau lebih cepat . Jika algoritma Anda adalah Big O dari n, maka itu juga secara otomatis Big O dari n persegi.

Big O n berarti algoritma saya berjalan setidaknya secepat ini. Anda tidak dapat melihat notasi Big O dari algoritma Anda dan mengatakan itu lambat. Anda hanya bisa mengatakannya dengan cepat.

Memeriksa ini keluar untuk tutorial video di Big O dari UC Berkley. Ini sebenarnya konsep sederhana. Jika Anda mendengar profesor Shewchuck (alias guru level Dewa) menjelaskannya, Anda akan berkata "Oh, itu saja!".

Saya menemukan penjelasan yang sangat bagus tentang notasi O besar terutama untuk seseorang yang tidak banyak ke matematika.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Notasi O besar digunakan dalam Ilmu Komputer untuk menggambarkan kinerja atau kompleksitas suatu algoritma. Big O secara khusus menjelaskan skenario terburuk, dan dapat digunakan untuk menggambarkan waktu eksekusi yang diperlukan atau ruang yang digunakan (misalnya dalam memori atau pada disk) oleh suatu algoritma.

Siapa pun yang membaca Pemrograman Mutiara atau buku Ilmu Komputer lainnya dan tidak memiliki landasan dalam Matematika akan menabrak dinding ketika mereka mencapai bab yang menyebutkan O (N log N) atau sintaksis lain yang tampaknya gila. Semoga artikel ini akan membantu Anda mendapatkan pemahaman tentang dasar-dasar Big O dan Logaritma.

Sebagai programmer pertama dan matematikawan kedua (atau mungkin ketiga atau keempat) saya menemukan cara terbaik untuk memahami Big O secara menyeluruh adalah dengan menghasilkan beberapa contoh dalam kode. Jadi, di bawah ini adalah beberapa perintah pertumbuhan bersama dengan deskripsi dan contoh di mana mungkin.

O (1)

O (1) menjelaskan suatu algoritma yang akan selalu dieksekusi dalam waktu (atau ruang) yang sama terlepas dari ukuran set data input.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

DI)

O (N) menjelaskan suatu algoritma yang kinerjanya akan tumbuh secara linear dan berbanding lurus dengan ukuran set data input. Contoh di bawah ini juga menunjukkan bagaimana Big O menyukai skenario kinerja terburuk; string yang cocok dapat ditemukan selama setiap iterasi dari for loop dan fungsi akan kembali lebih awal, tetapi notasi O Besar akan selalu menganggap batas atas di mana algoritma akan melakukan iterasi maksimum.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) merupakan algoritma yang kinerjanya berbanding lurus dengan kuadrat ukuran input data yang ditetapkan. Ini biasa terjadi pada algoritme yang melibatkan iterasi bersarang atas kumpulan data. Iterasi bersarang yang lebih dalam akan menghasilkan O (N ³ ), O (N ⁴ ) dll.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) menunjukkan suatu algoritma yang pertumbuhannya berlipat ganda dengan setiap penambahan pada set data input. Kurva pertumbuhan fungsi O (2 ^N ) adalah eksponensial - dimulai dari sangat dangkal, kemudian naik secara meteor. Contoh fungsi O (2 ^N ) adalah perhitungan rekursif angka Fibonacci:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logaritma

Logaritma sedikit lebih sulit untuk dijelaskan, jadi saya akan menggunakan contoh umum:

Pencarian biner adalah teknik yang digunakan untuk mencari kumpulan data yang diurutkan. Ia bekerja dengan memilih elemen tengah dari kumpulan data, pada dasarnya median, dan membandingkannya dengan nilai target. Jika nilainya cocok maka akan mengembalikan kesuksesan. Jika nilai target lebih tinggi dari nilai elemen probe, ia akan mengambil bagian atas kumpulan data dan melakukan operasi yang sama terhadapnya. Demikian juga, jika nilai target lebih rendah dari nilai elemen probe itu akan melakukan operasi terhadap bagian bawah. Itu akan terus membagi dua set data dengan setiap iterasi sampai nilai telah ditemukan atau sampai tidak dapat lagi membagi set data.

Jenis algoritma ini dideskripsikan sebagai O (log N). Mengurangi separuh dari kumpulan data yang dijelaskan dalam contoh pencarian biner menghasilkan kurva pertumbuhan yang memuncak di awal dan perlahan mendatar saat ukuran set data meningkat, misalnya set input data yang berisi 10 item membutuhkan satu detik untuk menyelesaikan, satu set data berisi 100 item membutuhkan dua detik, dan satu set data yang berisi 1000 item akan memakan waktu tiga detik. Menggandakan ukuran dari set data input memiliki sedikit efek pada pertumbuhannya karena setelah satu iterasi algoritma set data akan dibelah dua dan oleh karena itu setara dengan data input set setengah ukuran. Ini membuat algoritma seperti pencarian biner sangat efisien ketika berhadapan dengan set data besar.

Ini adalah penjelasan yang sangat disederhanakan, tetapi saya harap ini mencakup detail paling penting.

Katakanlah algoritma Anda menangani masalah tergantung pada beberapa 'faktor', misalnya mari kita buat N dan X.

Bergantung pada N dan X, algoritme Anda akan memerlukan beberapa operasi, misalnya dalam kasus terburuknya 3(N^2) + log(X)operasinya.

Karena Big-O tidak terlalu peduli dengan faktor konstan (alias 3), Big-O dari algoritma Anda adalah O(N^2 + log(X)). Ini pada dasarnya menerjemahkan 'jumlah operasi yang dibutuhkan algoritma Anda untuk skala kasus terburuk dengan ini'.

Kata pengantar

algoritma : prosedur / formula untuk memecahkan masalah

Bagaimana cara menganalisa algoritma dan bagaimana kita dapat membandingkan algoritma terhadap satu sama lain?

contoh: Anda dan seorang teman diminta untuk membuat fungsi untuk menjumlahkan angka dari 0 hingga N. Anda menghasilkan f (x) dan teman Anda menghasilkan g (x). Kedua fungsi memiliki hasil yang sama, tetapi algoritma yang berbeda. Untuk membandingkan secara objektif efisiensi dari algoritma, kami menggunakan notasi Big-O .

Notasi O-Besar: menjelaskan seberapa cepat runtime akan tumbuh relatif terhadap input saat input menjadi besar secara sewenang-wenang.

3 takeaways kunci:

1. Bandingkan seberapa cepat runtime tumbuh, TIDAK membandingkan runtime yang tepat (tergantung pada perangkat keras)
2. Hanya yang peduli dengan runtime yang tumbuh relatif terhadap input (n)
3. Ketika n menjadi besar secara sembarangan, fokuslah pada istilah yang akan tumbuh tercepat seiring n menjadi besar (pikirkan tak terbatas) AKA analisis asimptotik

Kompleksitas ruang: selain kompleksitas waktu, kami juga memperhatikan kompleksitas ruang (seberapa banyak memori / ruang yang digunakan algoritma). Alih-alih memeriksa waktu operasi, kami memeriksa ukuran alokasi memori.