Menentukan apakah Algoritma adalah O (log n)

25

Saya menyegarkan Teori CS saya, dan saya ingin tahu bagaimana mengidentifikasi bahwa algoritma O (log n) kompleksitas. Secara khusus, apakah ada cara mudah untuk mengidentifikasinya?

Saya tahu dengan O (n), Anda biasanya memiliki satu loop; O (n ^ 2) adalah loop ganda; O (n ^ 3) adalah triple loop, dll. Bagaimana dengan O (log n)?

algorithms complexity big-o Atif
sumber
2
stackoverflow.com/questions/749819/… atau ini benar-benar panjang dibaca: stackoverflow.com/questions/487258/…
wkl
Ah, itu satu-satunya tempat saya tidak melihat :)
Atif

Jawaban:

32

Saya tahu dengan O (n), Anda biasanya memiliki satu loop; O (n ^ 2) adalah loop ganda; O (n ^ 3) adalah triple loop, dll. Bagaimana dengan O (log n)?

Anda benar-benar melakukannya dengan cara yang salah di sini. Anda mencoba mengingat ekspresi O besar mana yang sesuai dengan struktur algoritmik yang diberikan, tetapi Anda harus benar-benar hanya menghitung jumlah operasi yang dibutuhkan algoritma dan membandingkannya dengan ukuran input. Algoritma yang mengulang seluruh inputnya memiliki kinerja O (n) karena menjalankan loop n kali, bukan karena memiliki loop tunggal. Inilah satu loop dengan kinerja O (log n):

for (i = 0; i < log2(input.count); i++) {
    doSomething(...);
}

Jadi, algoritma apa pun di mana jumlah operasi yang diperlukan adalah berdasarkan urutan logaritma ukuran input adalah O (log n). Hal penting yang diberitahukan oleh analisis big-O adalah bagaimana waktu eksekusi suatu algoritma berubah relatif terhadap ukuran input: jika Anda menggandakan ukuran input, apakah algoritma tersebut mengambil 1 langkah lebih banyak (O (log n)) , dua kali lebih banyak langkah (O (n)), empat kali lebih banyak langkah (O (n ^ 2)), dll.

Apakah itu membantu untuk mengetahui dari pengalaman bahwa algoritma yang berulang kali mempartisi input mereka biasanya memiliki 'log n' sebagai komponen kinerja mereka? Yakin. Tetapi jangan mencari partisi dan langsung ke kesimpulan bahwa kinerja algoritma adalah O (log n) - itu mungkin sesuatu seperti O (n log n), yang sangat berbeda.

Caleb
sumber
3
Perhatikan bahwa cara yang lebih sehari-hari untuk mengatakan "pada urutan logaritma ukuran" adalah dengan mengatakan "pada urutan jumlah digit dalam ukuran".
@ Caleb dasar sebenarnya dari logaritma tidak penting ketika berbicara penskalaan.
@Caleb berbicara mutlak tidak masuk akal dengan O besar. Sebuah kata-kata Anda mungkin suka lebih baik: ketika jumlah digit ganda, jumlah langkah ganda.
@Caleb berbicara mutlak tidak masuk akal dengan O besar. Sebuah kata-kata Anda mungkin suka lebih baik: ketika jumlah digit ganda, jumlah langkah ganda.
@ ThorbjørnRavnAndersen Ya, itulah yang dimaksud dengan "logaritma ukuran". Saya tidak yakin apa masalah Anda dengan frasa tersebut, kecuali Anda memilih untuk mengatakannya secara berbeda. Pada dasarnya, saya pikir kami setuju.
Caleb
25

Idenya adalah bahwa suatu algoritma adalah O(log n)jika alih-alih menelusuri struktur 1 demi 1, Anda membagi struktur menjadi dua berulang-ulang dan melakukan sejumlah operasi konstan untuk setiap pemisahan. Algoritme pencarian tempat ruang jawaban terus terpecah berada O(log n). Contohnya adalah pencarian biner , di mana Anda terus membelah array yang dipesan menjadi dua berulang-ulang sampai Anda menemukan nomornya.

Catatan: Anda tidak perlu menjadi membelah di bagian bahkan.

Casey Patton
sumber
1
Bagaimana jika saya membagi input menjadi dua dan kemudian iterate 2 ^ (n / 2) kali pada sisanya sebelum membaginya lagi? (Tentu saja saya tahu apa itu, saya hanya ingin menunjukkan contoh di mana pendekatan sederhana ini gagal).
Tamás Szelei
@ Oh, itu agak langka. Sangat langka saat mencari.
Donal Fellows
1
@DonalFellows Teori Algoritma bukanlah ilmu empiris. Dan pertanyaannya bukan tentang pencarian, hanya saja penyebutan log nrefleks pencarian biner yang dipicu pada orang.
Tamás Szelei
2
Partisi tidak membuat algoritma O (log n), itu (biasanya) menambahkan faktor log n ke batas O-besar. Jenis rekursif seperti heapsort dan mergesort adalah contoh sempurna: mereka mempartisi input, tetapi kemudian mereka secara rekursi mempartisi kedua partisi yang dihasilkan. Hasilnya adalah kinerja O (n log n).
Caleb
@ Afish: Poin bagus. Tujuan saya dengan jawaban ini adalah untuk membuatnya sesederhana mungkin mengingat sifat pertanyaan itu. Saya mengubah garis "Anda membagi struktur menjadi dua ..." menjadi "Anda membagi struktur menjadi dua ... dan melakukan sejumlah operasi konstan untuk setiap pemisahan" untuk mencoba mendapatkan titik ini di hanya dengan sederhana.
Casey Patton
2

Contoh khas adalah yang berhubungan dengan pencarian biner. Misalnya, algoritma pencarian biner biasanya O(log n).

Jika Anda memiliki pohon pencarian biner, cari , masukkan, dan hapus semuanya adalah O(log n)kompleksitas.

Setiap situasi di mana Anda terus-menerus mempartisi ruang akan sering melibatkan log nkomponen. Inilah sebabnya mengapa banyak algoritma pengurutan memiliki O(nlog n)kompleksitas, karena mereka sering mempartisi satu set dan mengurutkannya.

Kris Harper
sumber
1

Jika Anda menginginkannya sesederhana "loop tunggal -> O (n), loop ganda -> O (n ^ 2)", daripada jawabannya mungkin "Tree -> O (log n)". Lebih akurat melintasi pohon dari akar ke satu (tidak semua!) Daun atau sebaliknya. Namun, ini semua penyederhanaan yang berlebihan.

scarfridge
sumber
Jadi, apa yang salah dengan jawaban saya? Saya terbuka untuk kritik yang membangun.
scarfridge
0

Anda ingin tahu apakah ada cara mudah untuk mengidentifikasi apakah suatu algoritma adalah O (log N).

Nah: jalankan saja dan waktunya. Jalankan untuk input 1.000, 10.000, 100.000 dan sejuta.

Jika Anda melihat seperti waktu berjalan 3,4,5,6 detik (atau beberapa kelipatan) Anda dapat dengan aman mengatakan itu O (log N). Jika lebih seperti: 1,10,100,1000 detik maka mungkin O (N). Dan jika itu seperti 3.40.500.6000 detik maka itu O (N log N).

Pieter B
sumber
Setiap orang harus memberikan jawaban ini satu upvote dan satu downvote, keduanya karena alasan yang jelas :-)
gnasher729