Pertanyaan Apa arti O (log n) sebenarnya?


Saat ini saya sedang belajar tentang Notasi O Big berjalan kali dan amortisasi kali. Saya mengerti gagasan tentang Di) waktu linier, yang berarti bahwa ukuran input mempengaruhi pertumbuhan algoritma secara proporsional ... dan hal yang sama berlaku untuk, misalnya, waktu kuadrat Di2) etc..even algoritma, seperti generator permutasi, dengan Di!) kali, yang tumbuh oleh faktorial.

Misalnya, fungsi berikut ini Di) karena algoritma tumbuh secara proporsional dengan inputnya n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Demikian pula, jika ada loop nested, waktu akan menjadi O (n2).

Tapi sebenarnya apa itu O (log n)? Misalnya, apa artinya mengatakan bahwa ketinggian pohon biner lengkap O (log n)?

Saya tahu (mungkin tidak terlalu detail) apa Logarithm, dalam arti bahwa: log10 100 = 2, tetapi saya tidak dapat memahami cara mengidentifikasi fungsi dengan waktu logaritmik.


1732
2018-02-21 20:05


asal


Jawaban:


Saya tidak dapat memahami cara mengidentifikasi fungsi dengan waktu log.

Atribut yang paling umum dari fungsi run-time logaritmik adalah:

  • pilihan elemen berikutnya yang melakukan beberapa tindakan adalah salah satu dari beberapa kemungkinan, dan
  • hanya satu yang perlu dipilih.

atau

  • elemen di mana tindakan dilakukan adalah angka n

Inilah sebabnya, misalnya, mencari orang di buku telepon adalah O (log n). Anda tidak perlu memeriksanya setiap orang di buku telepon untuk menemukan yang benar; sebagai gantinya, Anda dapat dengan mudah membagi-dan-menaklukkan dengan melihat berdasarkan di mana nama mereka berdasarkan abjad, dan di setiap bagian Anda hanya perlu menjelajahi subset setiap bagian sebelum akhirnya Anda menemukan nomor telepon seseorang.

Tentu saja, buku telepon yang lebih besar akan tetap memakan waktu lebih lama, tetapi tidak akan tumbuh secepat peningkatan proporsional dalam ukuran tambahan.


Kita dapat memperluas contoh buku telepon untuk membandingkan jenis operasi lain dan mereka waktu berjalan. Kami akan menganggap buku telepon kami memiliki bisnis ("Halaman Kuning") yang memiliki nama unik dan orang-orang ("Halaman Putih") yang mungkin tidak memiliki nama yang unik. Nomor telepon diberikan kepada paling banyak satu orang atau bisnis. Kami juga akan menganggap bahwa dibutuhkan waktu yang konstan untuk beralih ke halaman tertentu.

Berikut ini adalah waktu berjalan dari beberapa operasi yang mungkin kami lakukan di buku telepon, dari yang terbaik hingga terburuk:

  • O (1) (kasus terbaik): Mengingat halaman yang menyebutkan nama bisnis dan nama bisnis, temukan nomor telepon.

  • O (1) (kasus rata-rata): Mengingat halaman yang menyebutkan nama seseorang dan namanya, temukan nomor teleponnya.

  • O (log n): Mengingat nama seseorang, temukan nomor telepon dengan memilih titik acak sekitar setengah dari bagian buku yang belum Anda cari, lalu periksa untuk melihat apakah nama orang tersebut pada saat itu. Kemudian ulangi proses sekitar separuh bagian buku di mana nama orang itu berada. (Ini adalah pencarian biner untuk nama seseorang.)

  • Di): Temukan semua orang yang nomor teleponnya berisi digit "5".

  • Di): Diberikan nomor telepon, temukan orang atau bisnis dengan nomor itu.

  • O (n log n): Ada campuran di kantor printer, dan buku telepon kami telah memasukkan semua halamannya dalam urutan acak. Perbaiki urutannya sehingga benar dengan melihat nama depan pada setiap halaman dan kemudian meletakkan halaman itu di tempat yang tepat di buku telepon baru yang kosong.

Untuk contoh di bawah ini, kita sekarang di kantor printer. Buku telepon sedang menunggu untuk dikirimkan ke setiap penduduk atau bisnis, dan ada stiker di setiap buku telepon yang mengidentifikasi ke mana harus dikirimkan. Setiap orang atau bisnis mendapat satu buku telepon.

  • O (n log n): Kami ingin mempersonalisasi buku telepon, jadi kami akan menemukan setiap orang atau nama bisnis di salinan yang mereka tunjuk, kemudian lingkari nama mereka di buku dan tuliskan ucapan terima kasih singkat untuk patronase mereka.

  • Di2): Kesalahan terjadi di kantor, dan setiap entri di setiap buku telepon memiliki tambahan "0" di ujung nomor telepon. Ambil beberapa warna putih dan keluarkan setiap nol.

  • O (n · n!): Kami siap memuat buku telepon ke dermaga pengiriman. Sayangnya, robot yang seharusnya memuat buku telah rusak: itu menempatkan buku-buku ke truk dalam urutan acak! Lebih buruk lagi, itu memuat semua buku ke truk, kemudian memeriksa untuk melihat apakah mereka berada di urutan yang benar, dan jika tidak, itu membebani mereka dan memulai kembali. (Ini yang ditakuti semacam bogo.)

  • Din): Anda memperbaiki robot sehingga memuat hal dengan benar. Keesokan harinya, salah satu rekan kerja Anda memainkan lelucon pada Anda dan mengirimkan robot dok pemuatan ke sistem pencetakan otomatis. Setiap kali robot pergi untuk memuat buku asli, printer pabrik membuat duplikat menjalankan semua buku telepon! Untungnya, sistem deteksi bug robot cukup canggih sehingga robot tidak mencoba mencetak lebih banyak salinan ketika menemukan duplikat buku untuk memuat, tetapi masih harus memuat setiap buku asli dan duplikat yang telah dicetak.


2177
2018-02-21 20:14



Banyak jawaban yang bagus telah diposkan ke pertanyaan ini, tetapi saya yakin kita benar-benar kehilangan satu yang penting - yaitu, jawaban yang diilustrasikan.

Apa artinya mengatakan bahwa ketinggian pohon biner lengkap adalah O (log n)?

Gambar berikut menggambarkan pohon biner. Perhatikan bagaimana setiap level mengandung dua kali lipat jumlah node dibandingkan dengan level di atas (karenanya biner):

Binary tree

Pencarian biner adalah contoh dengan kompleksitas O(log n). Anggaplah bahwa simpul di tingkat bawah pohon pada gambar 1 mewakili item dalam beberapa koleksi yang diurutkan. Pencarian biner adalah algoritma membagi-dan-menaklukkan, dan gambar menunjukkan bagaimana kita akan membutuhkan (paling banyak) 4 perbandingan untuk menemukan catatan yang kita cari dalam dataset 16 item ini.

Asumsikan kita punya dataset dengan 32 elemen. Lanjutkan gambar di atas untuk menemukan bahwa kita sekarang akan membutuhkan 5 perbandingan untuk menemukan apa yang kita cari, karena pohon hanya tumbuh satu tingkat lebih dalam ketika kita melipatgandakan jumlah data. Akibatnya, kompleksitas algoritma dapat digambarkan sebagai urutan logaritmik.

Merencanakan log(n) pada selembar kertas biasa, akan menghasilkan grafik di mana munculnya kurva melambat sebagai n meningkat:

O(log n)


509
2018-02-21 22:22



O(log N) pada dasarnya berarti waktu naik secara linier sementara n naik secara eksponensial. Jadi jika dibutuhkan 1 kedua untuk menghitung 10 elemen, akan dibutuhkan 2 detik untuk menghitung 100 elemen, 3 detik untuk menghitung 1000 elemen, dan sebagainya.

Itu O(log n) ketika kita membagi dan menaklukkan jenis algoritma, misalnya pencarian biner. Contoh lain adalah quick sort dimana setiap kali kita membagi array menjadi dua bagian dan setiap kali dibutuhkan O(N) waktu untuk menemukan elemen pivot. Maka itu N O(log N) 


463
2018-02-21 20:18



Penjelasan di bawah ini menggunakan kasus sepenuhnya seimbang pohon biner untuk membantu Anda memahami bagaimana kami mendapatkan kompleksitas waktu logaritmik.

Pohon biner adalah kasus di mana masalah ukuran n dibagi menjadi sub-masalah ukuran n / 2 sampai kita mencapai masalah ukuran 1:

height of a binary tree

Dan itulah bagaimana Anda mendapatkan O (log n) yang merupakan jumlah pekerjaan yang perlu dilakukan pada pohon di atas untuk mencapai solusi.

Algoritma umum dengan O (log n) kompleksitas waktu adalah Pencarian Biner yang relasional rekursifnya adalah T (n / 2) + O (1) yaitu pada setiap tingkat berikutnya dari pohon Anda membagi masalah menjadi setengah dan melakukan jumlah konstan pekerjaan tambahan.


196
2017-10-26 19:33



Jika Anda memiliki fungsi yang membutuhkan:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Maka dibutuhkan log2(n) waktu. Itu Notasi O besar, secara longgar, berarti bahwa hubungan hanya perlu berlaku untuk n besar, dan bahwa faktor konstan dan istilah yang lebih kecil dapat diabaikan.


120
2018-02-21 20:11



Ikhtisar

Yang lain telah memberikan contoh diagram yang baik, seperti diagram pohon. Saya tidak melihat contoh kode sederhana. Jadi, selain penjelasan saya, saya akan memberikan beberapa algoritma dengan pernyataan cetak sederhana untuk menggambarkan kompleksitas kategori algoritma yang berbeda.

Pertama, Anda akan ingin memiliki gagasan umum Logarithm, yang bisa Anda dapatkan https://en.wikipedia.org/wiki/Logarithm . Penggunaan ilmu alam e dan log natural. Murid teknik akan menggunakan log_10 (log basis 10) dan ilmuwan komputer akan menggunakan log_2 (basis log 2) banyak, karena komputer berbasis biner. Terkadang Anda akan melihat singkatan dari log natural sebagai ln(), insinyur biasanya membiarkan _10 mati dan hanya digunakan log() dan log_2 disingkat menjadi lg(). Semua jenis logaritma tumbuh dengan cara yang sama, itulah sebabnya mereka berbagi kategori yang sama log(n).

Ketika Anda melihat contoh kode di bawah ini, saya sarankan melihat O (1), lalu O (n), lalu O (n ^ 2). Setelah Anda baik dengan itu, lihatlah yang lain. Saya telah menyertakan contoh-contoh bersih serta variasi untuk menunjukkan bagaimana perubahan halus masih dapat menghasilkan kategorisasi yang sama.

Anda dapat menganggap O (1), O (n), O (logn), dll sebagai kelas atau kategori pertumbuhan. Beberapa kategori akan membutuhkan waktu lebih banyak daripada yang lain. Kategori-kategori ini membantu memberi kita cara memesan kinerja algoritma. Beberapa tumbuh lebih cepat ketika input n tumbuh. Tabel berikut menunjukkan pertumbuhan tersebut secara numerik. Dalam tabel di bawah ini, pikirkan log (n) sebagai langit-langit log_2.

enter image description here

Contoh Kode Sederhana Berbagai Kategori O Besar:

O (1) - Contoh Waktu Konstan:

  • Algoritma 1:

Algoritma 1 mencetak halo satu kali dan tidak bergantung pada n, sehingga akan selalu berjalan dalam waktu yang konstan, begitu juga O(1).

print "hello";
  • Algoritma 2:

Algoritma 2 mencetak halo 3 kali, namun tidak bergantung pada ukuran input. Bahkan ketika n tumbuh, algoritme ini akan selalu hanya mencetak halo 3 kali. Itu dikatakan 3, adalah konstanta, jadi algoritma ini juga O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Contoh Logarithmic:

  • Algoritma 3 - Ini bertindak seperti "log_2"

Algoritma 3 menunjukkan suatu algoritma yang berjalan di log_2 (n). Perhatikan operasi posting dari loop untuk mengalikan nilai saat ini dari i dengan 2, jadi i pergi dari 1 hingga 2 hingga 4 hingga 8 hingga 16 hingga 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algoritma 4 - Ini bertindak seperti "log_3"

Algoritma 4 menunjukkan log_3. Melihat i pergi dari 1 hingga 3 hingga 9 hingga 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algoritma 5 - Ini bertindak seperti "log_1.02"

Algoritma 5 adalah penting, karena membantu menunjukkan bahwa selama jumlahnya lebih besar dari 1 dan hasilnya berulang kali dikalikan melawan dirinya sendiri, bahwa Anda melihat algoritma logaritma.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Contoh Waktu Linear:

  • Algoritma 6

Algoritma ini sederhana, yang mencetak halo n kali.

for(int i = 0; i < n; i++)
  print "hello";
  • Algoritma 7

Algoritma ini menunjukkan variasi, di mana ia akan mencetak halo n / 2 kali. n / 2 = 1/2 * n. Kami mengabaikan konstanta 1/2 dan melihat bahwa algoritma ini adalah O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Contoh:

  • Algoritma 8

Anggap ini sebagai kombinasi dari O(log(n)) dan O(n). Sarang untuk loop membantu kami mendapatkan O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algoritma 9

Algoritma 9 adalah seperti algoritma 8, tetapi masing-masing loop telah memungkinkan variasi, yang masih menghasilkan hasil akhir O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n kuadrat Contoh:

  • Algoritma 10

O(n^2) diperoleh dengan mudah dengan bersarang standar untuk loop.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algoritma 11

Seperti algoritma 10, tetapi dengan beberapa variasi.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n potong dadu Contoh:

  • Algoritma 12

Ini seperti algoritma 10, tetapi dengan 3 loop bukan 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algoritma 13

Seperti algoritma 12, tetapi dengan beberapa variasi yang masih menghasilkan O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Ringkasan

Di atas memberikan beberapa contoh langsung, dan variasi untuk membantu menunjukkan perubahan halus apa yang dapat diperkenalkan yang benar-benar tidak mengubah analisis. Semoga ini memberi Anda wawasan yang cukup.


107
2018-04-26 22:50



Waktu berjalan logaritmik (O(log n)) pada dasarnya berarti waktu berjalan bertumbuh sebanding dengan logaritma ukuran input - sebagai contoh, jika 10 item membutuhkan waktu paling lama x, dan 100 item membutuhkan paling banyak, katakanlah, 2x, dan 10.000 item membutuhkan paling banyak 4x, maka itu terlihat seperti O(log n) kompleksitas waktu.


84
2018-02-21 20:10



Logaritma

Ok mari kita coba dan pahami sepenuhnya apa itu logaritma sebenarnya.

Bayangkan kita memiliki tali dan kita mengikatnya dengan kuda. Jika talinya langsung terikat pada kuda, kekuatan kuda harus menarik diri (katakanlah, dari seorang pria) secara langsung 1.

Sekarang bayangkan tali itu melingkar di sebuah tiang. Kuda yang melarikan diri sekarang harus menarik berkali-kali lebih keras. Jumlah waktu akan tergantung pada kekasaran tali dan ukuran tiang, tetapi mari kita asumsikan itu akan melipatgandakan kekuatan seseorang sebesar 10 (ketika tali itu membuat putaran lengkap).

Sekarang jika tali dilingkarkan sekali, kuda harus menarik 10 kali lebih keras. Jika manusia memutuskan untuk membuatnya benar-benar sulit untuk kuda, ia mungkin akan memutar tali lagi di sekitar tiang, meningkatkan kekuatannya dengan tambahan 10 kali. Putaran ketiga akan meningkatkan lagi kekuatan sebanyak 10 kali lebih lanjut.

enter image description here

Kita dapat melihat bahwa untuk setiap loop, nilainya meningkat sebesar 10. Jumlah belokan yang diperlukan untuk mendapatkan nomor apa pun disebut logaritma dari angka tersebut, yaitu kita membutuhkan 3 posting ke beberapa kekuatan Anda sebanyak 1000 kali, 6 posting untuk melipatgandakan kekuatan Anda dengan 1.000.000.

3 adalah logaritma 1.000, dan 6 adalah logaritma 1.000.000 (basis 10).

Jadi apa arti dari O (log n)? 

Dalam contoh kami di atas, 'tingkat pertumbuhan' kami adalah O (log n). Untuk setiap pengulangan tambahan, kekuatan yang dapat ditangani tali kami adalah 10 kali lebih banyak:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Sekarang contoh di atas memang menggunakan basis 10, tetapi untungnya basis log tidak signifikan ketika kita berbicara tentang notasi besar.

Sekarang mari kita bayangkan Anda mencoba menebak angka antara 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Sekarang butuh 7 tebakan untuk mendapatkan hak ini. Tapi apa hubungannya di sini? Berapa jumlah item terbanyak yang dapat Anda tebak dari setiap tebakan tambahan?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Dengan menggunakan grafik, kita dapat melihat bahwa jika kita menggunakan pencarian biner untuk menebak angka antara 1-100 itu akan membawa kita paling banyak 7 upaya. Jika kami memiliki 128 nomor, kami juga bisa menebak jumlah dalam 7 percobaan tetapi 129 nomor akan membawa kami paling banyak 8 upaya (dalam kaitannya dengan logaritma, di sini kita akan membutuhkan 7 tebakan untuk kisaran nilai 128, 10 tebakan untuk rentang nilai 1024. 7 adalah logaritma 128, 10 adalah logaritma 1024 (basis 2)).

Perhatikan bahwa saya telah menebalkan 'paling banyak'. Notasi besar selalu mengacu pada kasus yang lebih buruk. Jika Anda beruntung, Anda bisa menebak jumlahnya dalam satu upaya dan jadi kasus terbaik adalah O (1), tapi itu cerita lain.

Kita dapat melihat bahwa untuk setiap tebakan, kumpulan data kami menyusut. Aturan praktis yang baik untuk mengidentifikasi apakah suatu algoritma memiliki waktu logaritmik   untuk melihat apakah kumpulan data menyusut dengan urutan tertentu setelah setiap iterasi

Bagaimana dengan O (n log n)?

Anda akhirnya akan menemukan waktu linerarithmic O (n log (n) algoritma. Aturan praktis di atas berlaku lagi, tetapi kali ini fungsi logaritma harus dijalankan n kali mis. mengurangi ukuran daftar n kali, yang terjadi dalam algoritma seperti mergesort.

Anda dapat dengan mudah mengidentifikasi apakah waktu algoritmik adalah n log n. Carilah loop luar yang iterates melalui daftar (O (n)). Kemudian lihat untuk melihat apakah ada lingkaran dalam. Jika loop dalam adalah memotong / mengurangi kumpulan data pada setiap iterasi, loop itu (O (log n), dan algoritma keseluruhannya = O (n log n).

Penafian: Contoh tali-logaritma diambil dari yang sangat baik Buku Mathematician's Delight oleh W.Sawyer. 


55
2017-10-08 14:27



Anda dapat menganggap O (log N) secara intuitif dengan mengatakan waktu sebanding dengan jumlah digit di N.

Jika suatu operasi melakukan kerja waktu konstan pada setiap digit atau sedikit input, seluruh operasi akan memakan waktu sebanding dengan jumlah digit atau bit dalam input, bukan besarnya input; jadi, O (log N) daripada O (N).

Jika suatu operasi membuat serangkaian keputusan waktu konstan masing-masing yang membagi (mengurangi dengan faktor 3, 4, 5 ..) ukuran input yang akan dipertimbangkan, keseluruhan akan memakan waktu sebanding dengan basis log 2 (basis 3). , basis 4, basis 5 ...) dari ukuran N dari input, daripada O (N).

Dan seterusnya.


54
2018-02-21 20:13



Cara terbaik yang saya selalu harus memvisualisasikan secara mental algoritma yang berjalan di O (log n) adalah sebagai berikut:

Jika Anda meningkatkan ukuran masalah dengan jumlah perkalian (yaitu melipatgandakan ukurannya dengan 10), pekerjaan hanya ditingkatkan dengan jumlah tambahan.

Menerapkan ini ke pertanyaan pohon biner Anda sehingga Anda memiliki aplikasi yang baik: jika Anda menggandakan jumlah node dalam pohon biner, ketinggian hanya meningkat sebesar 1 (jumlah aditif). Jika Anda menggandakannya lagi, itu masih hanya meningkat 1. (Jelas saya menganggapnya tetap seimbang dan semacamnya). Dengan begitu, alih-alih menggandakan pekerjaan Anda ketika ukuran masalah dikalikan, Anda hanya melakukan sedikit lebih banyak pekerjaan. Itu sebabnya algoritma O (log n) mengagumkan.


48
2018-02-22 19:51