Apa itu O dalam Big O?

Apa yang Besar dan O dalam notasi Big O? Saya sudah membaca definisi dan tidak memberi tahu apa yang diucapkan O sebagai 'oh'. Sebagai contoh - Saya mengerti bahwa O (n) adalah kompleksitas dari algoritma linier di mana n bisa menjadi jumlah operasi. tapi apa itu O ?

Yah, tebakan saya adalah pesanan, yang bertepatan dengan wikipedia .

Sunting: (terjemahan saya sendiri (perbaikan apa pun dihargai)) dari artikel wikipedia Jerman

Huruf kapital O (sebenarnya omicron kapital pada waktu itu) sebagai simbol untuk urutan (Jerman: "Ordnung von") pertama kali digunakan oleh ahli teori bilangan Jerman Paul Bachman dalam edisi kedua bukunya tentang teori bilangan analitik muncul pada tahun 1894. Notasi ini mendapatkan popularitas karena karya Edmund Landau, ahli teori bilangan Jerman lainnya, yang nomenklatur ini secara luas dikaitkan dengan hari ini, terutama dalam terminologi Jerman.

"Besar" berarti "modal", dan "O" berarti ketertiban, seperti dalam "urutan kompleksitas". Dinamakan demikian karena konvensi penulisan "urutan kompleksitas" sebagai O (f (x)), misalnya, dengan huruf kapital 'O', atau 'O Besar'. Tidak ada yang banyak membicarakannya karena 'semua orang' mengerti apa artinya, dan memahaminya tidak benar-benar membantu Anda memahami analisis kompleksitas.

Untuk pemahaman tentang analisis kompleksitas, saya pikir tautan yang diposting oleh topgun_ivard adalah tempat yang baik untuk memulai. Buku teks pengantar yang baik yang mencakup struktur data atau algoritma juga dapat membantu.

O berarti ketertiban.

Ini awalnya diperkenalkan oleh ahli matematika Jerman Paul Bachmann dalam volume kedua bukunya tentang teori bilangan Die Analytische Zahlentheorie , yang diterbitkan pada 1894 (hal. 401) . Dia mencatat, setelah formula tempat dia pertama kali menggunakan notasi:

(...) wenn wir durch das Zeichen O (n) einde Grösse ausdrücken, deren Ordnung di Bezug auf n die Ordnung von n nicht überschreitet (...)

Terjemahan saya:

(...) di mana dengan notasi O (n) kami menunjukkan besarnya urutan dengan referensi n tidak melebihi urutan n (...)

Berbeda dengan apa yang dikatakan orang lain, tidak ada dalam teksnya yang menunjukkan bahwa ini sebenarnya adalah ibu kota Yunani omikron. Dia menggunakan banyak karakter Yunani dan Latin, jadi sebenarnya tidak ada cara untuk mengatakannya. Mengingat terus menggunakan "Ordnung n log n " dll dalam teks itu jelas bahwa itu adalah singkatan dari "Ordnung" (bahasa Jerman untuk "pesanan" jika ada keraguan) dalam hal apapun, tetapi itu masih bisa membiarkan penggunaan penggunaan terbuka sebuah O Yunani yang mewah

Namun, asal mula omikron lebih cenderung retronim karena Donald Knuth yang memperkenalkan simbol omega (Ω) dan theta (Θ) untuk konsep terkait dalam makalahnya Big Omicron dan Big Omega dan Big Theta , atau mungkin Hardy dan Littlewood yang memperkenalkan simbol omega sebelumnya.

Saya suka artikel ini , berharap Anda akan merasakan manfaatnya juga!

Mengutip bagian dari artikel:
Huruf Yunani Besar

Big O sering disalahgunakan. Big O atau Big Oh sebenarnya adalah kependekan dari Big Omicron. Ini mewakili batas atas kompleksitas asimptotik. Jadi jika suatu algoritma adalah O (n log n) ada konstanta c sedemikian rupa sehingga batas atas adalah cn log n.

Θ (n log n) (Big Theta) lebih terikat dari itu. Algoritma semacam itu berarti ada dua konstanta c1 dan c2 sedemikian rupa sehingga c1n log n <f (n) <c2n log n.

Ω (n log n) (Omega Besar) mengatakan bahwa algoritma memiliki batas cn log yang lebih rendah.

Ada yang lain tetapi ini adalah yang paling umum dan Big O adalah yang paling umum dari semua. Perbedaan seperti itu biasanya tidak penting tetapi perlu dicatat. Notasi yang benar adalah notasi yang benar.

Apa itu Big O?

Notasi O besar berusaha untuk menggambarkan kompleksitas relatif dari suatu algoritma dengan mengurangi tingkat pertumbuhan ke faktor-faktor kunci ketika faktor kunci cenderung menuju tak terbatas. Karena alasan ini, Anda akan sering mendengar ungkapan kompleksitas asimptotik. Dengan demikian, semua faktor lain diabaikan. Ini adalah representasi relatif dari kompleksitas.

Apa Bukan Big O?

Big O bukanlah tes kinerja suatu algoritma. Ini juga bersifat nosional atau abstrak karena cenderung mengabaikan faktor-faktor lain. Kompleksitas algoritma pengurutan biasanya dikurangi menjadi jumlah elemen yang diurutkan sebagai faktor kunci. Ini baik-baik saja tetapi tidak memperhitungkan masalah akun seperti:

Penggunaan Memori: satu algoritma mungkin menggunakan lebih banyak memori daripada yang lain. Bergantung pada situasinya, ini bisa berupa apa pun dari yang sama sekali tidak relevan hingga kritis; Biaya Perbandingan: Mungkin saja membandingkan elemen sangat mahal, yang berpotensi akan mengubah perbandingan dunia nyata antara algoritma; Biaya Elemen Bergerak: elemen penyalinan biasanya murah tetapi hal ini belum tentu demikian; dll.

"f (x) besar-oh dari g (x)"

Ini adalah cara matematika untuk memprediksi pertumbuhan fungsi.

Biarkan f dan g menjadi fungsi dari himpunan bilangan bulat atau himpunan atau bilangan real ke himpunan bilangan real. Kita mengatakan bahwa f (x) adalah O (g (x)) jika ada konstanta C dan k sedemikian sehingga | f (x) | <= C | g (x) | dimanapun x> k.

Anda akan membaca ini sebagai "f (x) adalah besar-oh dari g (x)"

Big-O kadang-kadang disebut simbol Landau setelah ahli matematika Jerman Edmund Landau. Saya tidak berpikir itu berarti apa pun selain itu. Anda juga memiliki notasi Omega-besar dan Theta yang serupa. Simbol yang sewenang-wenang seperti biasa menggunakan theta untuk menunjukkan sudut dalam segitiga Anda berada di kelas Planar Geometry SMA Anda.

Correction @ back2dos telah memberikan penjelasan yang memuaskan untuk O sebagai merujuk pada pesanan. Kerja bagus. Lihat jawabannya.

Donald Knuth menerapkannya untuk mempelajari kompleksitas program komputer.

Jika Anda ingin menemukan alasan notasi digunakan, Anda harus membaca

"Analytische Zahlentheorie" oleh Paul Bachmann dari 1892

EDIT: Ternyata saya salah. Namun demikian, mungkin ini membantu seseorang menjaga simbolnya tetap lurus, jadi saya tidak akan menghapusnya.

Sebenarnya, itu bukan huruf Latin. Oh , itu huruf Yunani, Omicron . Sayangnya, keduanya memiliki mesin terbang yang sama persis, jadi, seiring waktu, versi aslinya rusak, dan sekarang hanya Oh .

Pilihan simbol sebenarnya tidak memiliki makna tertentu, itu dipilih sebagai perangkat mnemonik :

• Omicron memiliki huruf MICRO di dalamnya, dan semantik simbol Omicron secara kasar berarti "lebih kecil dari"
• Omega memiliki huruf MEGA di dalamnya, dan semantik simbol Omega kira-kira berarti "lebih besar dari"
• Theta (Θ) terlihat agak seperti tanda sama dengan, dan semantik simbol Theta secara kasar berarti "sama dengan"

Itu dia. Tidak ada makna nyata untuk itu, itu hanya permainan kata-kata, jika Anda mau, untuk membantu Anda mengingat semantik dengan lebih mudah.

UPDATE: Mencoba untuk membersihkan jawaban saya dan menjadi lebih akurat

Notasi O besar adalah cara untuk mengkarakterisasi fungsi sesuai dengan tingkat pertumbuhan di sana. O adalah singkatan dari order (order pertama adalah n order kedua sedang n-kuadrat dll). Dan jika saya tidak salah ini akan menjadi skenario kasus terburuk untuk metode runtime (atau penyimpanan) yang diberikan elemen N. Semakin besar urutannya, semakin buruk kinerjanya.
Sebagai contoh mencari catatan dalam array adalah O (1) (Saya percaya pada beberapa implementasi dari tabel hash yang juga terjadi). Menambahkan nilai ke akhir daftar tautan adalah O (N) karena Anda harus sampai ke akhir daftar sebelum Anda dapat menambahkan elemen dll.

Jawaban ini harusnya sedikit lebih benar daripada upaya pertama saya :)