Pengetahuan saya tentang big-O terbatas, dan ketika istilah log muncul dalam persamaan, hal itu membuat saya semakin marah.

Bisakah seseorang menjelaskan kepada saya secara sederhana apa itu O(log n)algoritma? Dari manakah asal logaritma?

Ini secara khusus muncul ketika saya mencoba menyelesaikan pertanyaan latihan paruh waktu ini:

Misalkan X (1..n) dan Y (1..n) berisi dua daftar bilangan bulat, masing-masing diurutkan dalam urutan nondecreasing. Berikan algoritme waktu-O (log n) untuk mencari median (atau bilangan bulat terkecil ke-n) dari semua elemen gabungan 2n. Misalnya, X = (4, 5, 7, 8, 9) dan Y = (3, 5, 8, 9, 10), maka 7 adalah median dari daftar gabungan (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Petunjuk: gunakan konsep pencarian biner]

Saya harus setuju bahwa ini cukup aneh saat pertama kali Anda melihat algoritma O (log n) ... dari mana asal logaritma itu? Namun, ternyata ada beberapa cara berbeda yang membuat istilah log muncul di notasi O besar. Berikut ini beberapa di antaranya:

Membagi berulang kali dengan konstanta

Ambil nomor apa saja n; katakanlah, 16. Berapa kali kamu bisa membagi n dengan dua sebelum kamu mendapatkan angka yang kurang dari atau sama dengan satu? Untuk 16, kami punya itu

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Perhatikan bahwa ini akhirnya membutuhkan empat langkah untuk diselesaikan. Menariknya, kita juga punya log ₂ 16 = 4. Hmmm ... bagaimana dengan 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Ini membutuhkan tujuh langkah, dan log ₂ 128 = 7. Apakah ini kebetulan? Nggak! Ada alasan bagus untuk ini. Misalkan kita membagi bilangan n dengan 2 i kali. Kemudian kita mendapatkan nomor n / 2 ⁱ . Jika kita ingin menyelesaikan nilai i di mana nilai ini paling banyak 1, kita dapatkan

n / 2 ^saya ≤ 1

n ≤ 2 ⁱ

log ₂ n ≤ i

Dengan kata lain, jika kita memilih bilangan bulat i sedemikian rupa sehingga i ≥ log ₂ n, maka setelah membagi n menjadi setengah kali i kita akan mendapatkan nilai paling banyak 1. I terkecil yang dijamin adalah log ₂ n, jadi jika kita memiliki algoritma yang membagi dengan 2 hingga jumlahnya menjadi cukup kecil, maka kita dapat mengatakan bahwa itu berakhir dalam langkah O (log n).

Detail penting adalah bahwa tidak masalah konstanta apa yang Anda bagi dengan n (asalkan lebih besar dari satu); jika Anda membagi dengan konstanta k, dibutuhkan log _k n langkah untuk mencapai 1. Jadi, setiap algoritma yang berulang kali membagi ukuran input dengan beberapa pecahan akan membutuhkan iterasi O (log n) untuk berhenti. Iterasi tersebut mungkin membutuhkan banyak waktu dan waktu proses bersih tidak perlu O (log n), tetapi jumlah langkah akan menjadi logaritmik.

Jadi, dari mana ini muncul? Salah satu contoh klasik adalah pencarian biner , algoritma cepat untuk mencari nilai array yang diurutkan. Algoritme bekerja seperti ini:

• Jika larik kosong, kembalikan elemen tersebut tidak ada dalam larik.
• Jika tidak:
  • Lihatlah elemen tengah dari array.
  • Jika itu sama dengan elemen yang kita cari, kembalikan kesuksesan.
  • Jika lebih besar dari elemen yang kita cari:
    • Buang paruh kedua larik.
    • Ulang
  • Jika kurang dari elemen yang kita cari:
    • Buang paruh pertama larik.
    • Ulang

Misalnya, untuk mencari 5 dalam larik

1   3   5   7   9   11   13

Pertama-tama kita akan melihat elemen tengah:

1   3   5   7   9   11   13
            ^

Karena 7> 5, dan karena array sudah diurutkan, kita tahu pasti bahwa angka 5 tidak boleh berada di bagian belakang array, jadi kita bisa membuangnya. Daun ini

1   3   5

Jadi sekarang kita melihat elemen tengah di sini:

1   3   5
    ^

Karena 3 <5, kita tahu bahwa 5 tidak bisa muncul di paruh pertama larik, jadi kita bisa membuang larik separuh pertama untuk keluar.

        5

Sekali lagi kita melihat bagian tengah dari larik ini:

        5
        ^

Karena ini persis dengan angka yang kita cari, kita dapat melaporkan bahwa 5 memang ada dalam larik.

Jadi seberapa efisien ini? Nah, pada setiap iterasi kami membuang setidaknya setengah dari elemen array yang tersisa. Algoritme berhenti segera setelah array kosong atau kita menemukan nilai yang kita inginkan. Dalam kasus terburuk, elemen tidak ada, jadi kami terus membagi dua ukuran array hingga kami kehabisan elemen. Berapa lama waktu yang dibutuhkan? Nah, karena kita terus memotong array menjadi dua lagi dan lagi, kita akan menyelesaikan paling banyak iterasi O (log n), karena kita tidak dapat memotong array menjadi setengah lebih dari O (log n) kali sebelum kita menjalankannya. keluar dari elemen array.

Algoritme yang mengikuti teknik umum bagi-dan-taklukkan (memotong masalah menjadi beberapa bagian, menyelesaikan bagian-bagian itu, kemudian menyatukan masalah kembali) cenderung memiliki istilah logaritmik di dalamnya karena alasan yang sama - Anda tidak dapat terus memotong beberapa objek setengah lebih dari O (log n) kali. Anda mungkin ingin melihat merge sort sebagai contoh yang bagus untuk ini.

Memproses nilai satu digit pada satu waktu

Berapa digit dalam bilangan basis-10 n? Nah, jika ada angka k dalam bilangan tersebut, maka kita akan mendapatkan bahwa digit terbesar adalah kelipatan 10 ^k . Angka k-digit terbesar adalah 999 ... 9, k kali, dan ini sama dengan 10 ^{k + 1} - 1. Akibatnya, jika kita mengetahui bahwa n memiliki k digit di dalamnya, maka kita tahu bahwa nilai n adalah paling banyak 10 ^{k + 1} - 1. Jika kita ingin menyelesaikan k dalam suku-suku dari n, kita dapatkan

n ≤ 10 ^{k + 1} - 1

n + 1 ≤ 10 ^{k + 1}

log ₁₀ (n + 1) ≤ k + 1

(log ₁₀ (n + 1)) - 1 ≤ k

Dari sini kita mendapatkan bahwa k kira-kira adalah logaritma basis 10 dari n. Dengan kata lain, banyaknya digit di n adalah O (log n).

Misalnya, mari kita pikirkan kerumitan menambahkan dua angka besar yang terlalu besar untuk dimasukkan ke dalam kata mesin. Misalkan kita memiliki bilangan-bilangan tersebut yang direpresentasikan dalam basis 10, dan kita akan memanggil bilangan tersebut m dan n. Salah satu cara untuk menambahkannya adalah melalui metode sekolah dasar - tulis angka satu digit pada satu waktu, lalu kerjakan dari kanan ke kiri. Misalnya, untuk menjumlahkan 1337 dan 2065, kita akan mulai dengan menuliskan angka sebagai

    1  3  3  7
+   2  0  6  5
==============

Kami menambahkan digit terakhir dan membawa 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Kemudian kita menambahkan digit kedua-ke-terakhir ("kedua dari belakang") dan membawa 1:

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

Selanjutnya, kami menambahkan digit ketiga-ke-terakhir ("antepenultimate"):

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

Terakhir, kami menambahkan digit keempat hingga terakhir ("preantepenultimate" ... Saya suka bahasa Inggris):

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

Sekarang, berapa banyak pekerjaan yang kita lakukan? Kami melakukan total O (1) pekerjaan per digit (yaitu, jumlah pekerjaan yang konstan), dan ada total digit O (max {log n, log m}) yang perlu diproses. Ini memberikan total kompleksitas O (max {log n, log m}), karena kita perlu mengunjungi setiap digit dalam dua angka.

Banyak algoritme mendapatkan istilah O (log n) di dalamnya dari bekerja satu digit pada satu waktu di beberapa basis. Contoh klasiknya adalah radix sort , yang mengurutkan bilangan bulat satu digit dalam satu waktu. Ada banyak ragam jenis radix, tetapi biasanya dijalankan dalam waktu O (n log U), di mana U adalah bilangan bulat terbesar yang sedang diurutkan. Alasan untuk ini adalah bahwa setiap lintasan pengurutan membutuhkan waktu O (n), dan ada total iterasi O (log U) yang diperlukan untuk memproses setiap digit O (log U) dari bilangan terbesar yang diurutkan. Banyak algoritme tingkat lanjut, seperti algoritme jalur terpendek Gabow atau versi penskalaan algoritme aliran maks Ford-Fulkerson , memiliki istilah log dalam kompleksitasnya karena algoritme tersebut bekerja satu digit pada satu waktu.

Mengenai pertanyaan kedua Anda tentang bagaimana Anda memecahkan masalah itu, Anda mungkin ingin melihat pertanyaan terkait ini yang mengeksplorasi aplikasi yang lebih maju. Mengingat struktur umum masalah yang dijelaskan di sini, Anda sekarang dapat memiliki pemahaman yang lebih baik tentang bagaimana memikirkan masalah saat Anda mengetahui ada istilah log dalam hasil, jadi saya akan menyarankan agar Anda tidak melihat jawabannya sampai Anda memberikannya. beberapa pemikiran.

Semoga ini membantu!

Ketika kita berbicara tentang deskripsi besar-Oh, kita biasanya berbicara tentang waktu yang dibutuhkan untuk menyelesaikan masalah dengan ukuran tertentu . Dan biasanya, untuk masalah sederhana, ukuran itu hanya ditandai dengan jumlah elemen masukan, dan itu biasanya disebut n, atau N. (Jelas itu tidak selalu benar-- masalah dengan grafik sering dicirikan dalam jumlah simpul, V, dan jumlah sisi, E; tetapi untuk saat ini, kita akan berbicara tentang daftar objek, dengan N objek dalam daftar.)

Kami mengatakan bahwa masalah "adalah besar-Oh dari (beberapa fungsi N)" jika dan hanya jika :

Untuk semua N> beberapa sembarang N_0, ada beberapa konstanta c, sehingga runtime algoritme kurang dari konstanta c kali (beberapa fungsi N.)

Dengan kata lain, jangan berpikir tentang masalah kecil di mana "overhead konstan" dari menyiapkan masalah itu penting, pikirkan tentang masalah besar. Dan ketika memikirkan masalah besar, besar-Oh dari (beberapa fungsi N) berarti bahwa run-time masih selalu kurang dari beberapa kali konstan fungsi itu. Selalu.

Singkatnya, fungsi itu adalah batas atas, hingga faktor konstan.

Jadi, "besar-Oh dari log (n)" berarti sama dengan yang saya katakan di atas, kecuali "beberapa fungsi N" diganti dengan "log (n)".

Jadi, masalah Anda meminta Anda untuk memikirkan tentang pencarian biner, jadi mari kita pikirkan tentang itu. Misalkan Anda memiliki, katakanlah, daftar elemen N yang diurutkan dalam urutan meningkat. Anda ingin mengetahui apakah ada nomor tertentu dalam daftar itu. Salah satu cara untuk melakukan yang bukan merupakan pencarian biner adalah dengan memindai setiap elemen dari daftar dan melihat apakah itu nomor target Anda. Anda mungkin beruntung dan menemukannya pada percobaan pertama. Tetapi dalam kasus terburuk, Anda akan memeriksa N waktu yang berbeda. Ini bukan pencarian biner, dan ini bukan besar-Oh dari log (N) karena tidak ada cara untuk memaksanya masuk ke dalam kriteria yang kita buat sketsa di atas.

Anda dapat memilih konstanta arbitrer itu menjadi c = 10, dan jika daftar Anda memiliki N = 32 elemen, Anda baik-baik saja: 10 * log (32) = 50, yang lebih besar dari runtime 32. Tetapi jika N = 64 , 10 * log (64) = 60, yang kurang dari waktu proses 64. Anda dapat memilih c = 100, atau 1000, atau trilyun, dan Anda masih dapat menemukan beberapa N yang melanggar persyaratan tersebut. Dengan kata lain, tidak ada N_0.

Jika kita melakukan pencarian biner, kita memilih elemen tengah, dan membuat perbandingan. Kemudian kita membuang setengah angka, dan melakukannya lagi, dan lagi, dan seterusnya. Jika N = 32 Anda, Anda hanya dapat melakukannya sekitar 5 kali, yaitu log (32). Jika N = 64 Anda, Anda hanya dapat melakukan ini sekitar 6 kali, dll. Sekarang Anda dapat memilih konstanta sembarang c, sedemikian rupa sehingga persyaratan selalu dipenuhi untuk nilai N. yang besar.

Dengan semua latar belakang itu, yang biasanya berarti O (log (N)) adalah bahwa Anda memiliki beberapa cara untuk melakukan sesuatu yang sederhana, yang memotong ukuran masalah Anda menjadi dua. Sama seperti pencarian biner yang dilakukan di atas. Setelah Anda memotong masalah menjadi dua, Anda dapat memotongnya menjadi dua lagi, dan lagi, dan lagi. Namun, yang terpenting, yang tidak dapat Anda lakukan adalah beberapa langkah pemrosesan awal yang akan memakan waktu lebih lama dari waktu O (log (N)) tersebut. Jadi misalnya, Anda tidak dapat mengocok dua daftar Anda menjadi satu daftar besar, kecuali Anda dapat menemukan cara untuk melakukannya dalam waktu O (log (N)) juga.

(CATATAN: Hampir selalu, Log (N) berarti log-base-dua, yang saya asumsikan di atas.)

Dalam solusi berikut, semua baris dengan panggilan rekursif dilakukan pada setengah dari ukuran sub-array X dan Y yang diberikan. Baris lain dilakukan dalam waktu konstan. Fungsi rekursifnya adalah T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).

Anda mulai dengan MEDIAN (X, 1, n, Y, 1, n).

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)

Istilah Log sangat sering muncul dalam analisis kompleksitas algoritme. Berikut beberapa penjelasannya:

1. Bagaimana Anda merepresentasikan sebuah angka?

Mari kita ambil angka X = 245436. Notasi "245436" ini mengandung informasi implisit di dalamnya. Membuat informasi itu eksplisit:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

Yang merupakan perluasan desimal dari angka tersebut. Jadi, jumlah minimum informasi yang kami butuhkan untuk mewakili angka ini adalah 6 digit. Ini bukan kebetulan, karena angka apa pun yang kurang dari 10 ^ d dapat direpresentasikan dalam digit d .

Jadi berapa digit yang dibutuhkan untuk mewakili X? Itu sama dengan eksponen terbesar dari 10 di X plus 1.

==> 10 ^ d> X
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // Dan log muncul lagi ...
==> d = lantai (log (x)) + 1

Perhatikan juga bahwa ini adalah cara paling ringkas untuk menunjukkan angka dalam rentang ini. Setiap pengurangan akan menyebabkan hilangnya informasi, karena digit yang hilang dapat dipetakan ke 10 nomor lainnya. Contoh: 12 * dapat dipetakan menjadi 120, 121, 122,…, 129.

2. Bagaimana Anda mencari angka dalam (0, N - 1)?

Mengambil N = 10 ^ d, kami menggunakan pengamatan terpenting kami:

Jumlah informasi minimum untuk mengidentifikasi nilai secara unik dalam rentang antara 0 hingga N - 1 = log (N) digit.

Ini menyiratkan bahwa, ketika diminta untuk mencari nomor pada garis bilangan bulat, mulai dari 0 hingga N - 1, kita memerlukan setidaknya log (N) mencoba menemukannya. Mengapa? Algoritme pencarian apa pun harus memilih satu digit demi digit dalam pencariannya untuk nomor tersebut.

Jumlah minimum digit yang perlu dipilih adalah log (N). Oleh karena itu, jumlah minimum operasi yang dilakukan untuk mencari bilangan dalam ruang berukuran N adalah log (N).

Dapatkah Anda menebak kompleksitas urutan pencarian biner, pencarian terner atau pencarian deka?
Ini O (log (N))!

3. Bagaimana Anda mengurutkan sekumpulan angka?

Ketika diminta untuk mengurutkan sekumpulan angka A ke dalam array B, berikut tampilannya ->

Elemen Permute

Setiap elemen dalam larik asli harus dipetakan ke indeks yang sesuai di larik yang diurutkan. Jadi, untuk elemen pertama, kami memiliki n posisi. Untuk menemukan indeks yang sesuai dengan benar dalam kisaran ini dari 0 hingga n - 1, kita membutuhkan… operasi log (n).

Elemen berikutnya membutuhkan operasi log (n-1), log berikutnya (n-2), dan seterusnya. Totalnya menjadi:

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)

Menggunakan log (a) + log (b) = log (a * b),

==> log (n!)

Ini dapat diperkirakan menjadi nlog (n) - n.
Yang mana O (n * log (n))!

Oleh karena itu kami menyimpulkan bahwa tidak ada algoritma pengurutan yang dapat melakukan lebih baik daripada O (n * log (n)). Dan beberapa algoritme yang memiliki kerumitan ini adalah Gabung Sortir dan Urutan Heap yang populer!

Ini adalah beberapa alasan mengapa kami melihat log (n) begitu sering muncul dalam analisis kompleksitas algoritme. Hal yang sama dapat diperluas ke bilangan biner. Saya membuat video tentang itu di sini.
Mengapa log (n) muncul begitu sering selama analisis kompleksitas algoritma?

Bersulang!

Kami menyebut kompleksitas waktu O (log n), ketika solusi didasarkan pada iterasi di atas n, di mana pekerjaan yang dilakukan di setiap iterasi adalah sebagian kecil dari iterasi sebelumnya, karena algoritme bekerja menuju solusi.

Belum bisa berkomentar ... necro itu! Jawaban Avi Cohen salah, coba:

X = 1 3 4 5 8
Y = 2 5 6 7 9

Tidak ada kondisi yang benar, jadi MEDIAN (X, p, q, Y, j, k) akan memotong kedua kelima. Ini adalah urutan nondecreasing, tidak semua nilai berbeda.

Coba juga contoh panjang genap ini dengan nilai berbeda:

X = 1 3 4 7
Y = 2 5 6 8

Sekarang MEDIAN (X, p, q, Y, j + 1, k) akan memotong keempatnya.

Sebagai gantinya saya menawarkan algoritma ini, sebut dengan MEDIAN (1, n, 1, n):

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}