Apa arti O (log n) sebenarnya?

Saya belajar tentang waktu O Notasi Besar berjalan dan waktu diamortisasi. Saya memahami gagasan O (n) waktu linear, yang berarti bahwa ukuran input mempengaruhi pertumbuhan algoritma secara proporsional ... dan hal yang sama berlaku untuk, misalnya, waktu kuadrat O (n ² ) dll. Bahkan algoritma , seperti generator permutasi, dengan O (n!) kali, yang tumbuh secara faktorial.

Sebagai contoh, fungsi berikut adalah O (n) karena algoritma tumbuh sebanding dengan inputnya n :

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

Demikian pula, jika ada loop bersarang, waktu akan menjadi O (n ² ).

Tapi apa sebenarnya O (log n) ? Sebagai contoh, apa artinya mengatakan bahwa ketinggian pohon biner lengkap adalah O (log n) ?

Saya tahu (mungkin tidak dengan sangat terperinci) apa itu Logaritma, dalam arti bahwa: log ₁₀ 100 = 2, tetapi saya tidak dapat memahami bagaimana mengidentifikasi suatu fungsi dengan waktu logaritma.

Saya tidak mengerti bagaimana mengidentifikasi suatu fungsi dengan waktu log.

Atribut paling umum dari fungsi waktu berjalan logaritmik adalah:

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

atau

• elemen di mana tindakan dilakukan adalah digit n

Inilah sebabnya, misalnya, mencari orang di buku telepon adalah O (log n). Anda tidak perlu memeriksa setiap orang di buku telepon untuk menemukan yang tepat; alih-alih, Anda bisa membagi dan menaklukkannya dengan melihat berdasarkan di mana nama mereka berdasarkan abjad, dan di setiap bagian Anda hanya perlu menjelajahi subset dari setiap bagian sebelum akhirnya menemukan nomor telepon seseorang.

Tentu saja, buku telepon yang lebih besar masih akan membawa Anda lebih lama, tetapi itu tidak akan tumbuh secepat peningkatan proporsional dalam ukuran tambahan.

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

Berikut adalah waktu berjalan dari beberapa operasi yang mungkin kami lakukan di buku telepon, dari yang tercepat hingga yang paling lambat:

• O (1) (dalam kasus terburuk): Mengingat halaman tempat nama bisnis itu aktif dan nama bisnisnya, temukan nomor teleponnya.

• O (1) (dalam kasus rata-rata): Diberikan halaman tempat seseorang menggunakan nama mereka, temukan nomor teleponnya.

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

• O (n): Temukan semua orang yang nomor teleponnya berisi digit "5".

• O (n): Diberi nomor telepon, cari orang atau bisnis dengan nomor itu.

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

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

• O (n log n): Kami ingin mempersonalisasi buku telepon, jadi kami akan menemukan masing-masing orang atau nama bisnis dalam salinan yang ditunjuk, kemudian lingkari nama mereka di buku itu dan tulis catatan singkat terima kasih atas dukungan mereka. .

• O (n ² ): Terjadi kesalahan di kantor, dan setiap entri di masing-masing buku telepon memiliki "0" tambahan di akhir nomor telepon. Ambil beberapa white-out dan hapus setiap nol.

• O (n · n!): Kami siap memuat buku telepon ke dok pengiriman. Sayangnya, robot yang seharusnya memuat buku-buku itu menjadi berantakan: menempatkan buku-buku itu ke truk dalam urutan acak! Lebih buruk lagi, memuat semua buku ke truk, lalu memeriksa untuk melihat apakah mereka berada dalam urutan yang benar, dan jika tidak, itu membongkar mereka dan mulai lagi. (Ini adalah jenis bogo yang ditakuti .)

• O (n ⁿ ): Anda memperbaiki robot sehingga memuat semuanya dengan benar. Hari berikutnya, salah satu rekan kerja Anda mengerjai Anda dan mengirimkan robot dock loading ke sistem pencetakan otomatis. Setiap kali robot memuat buku asli, printer pabrik membuat duplikat semua buku telepon! Untungnya, sistem deteksi bug robot cukup canggih sehingga robot tidak mencoba mencetak lebih banyak salinan ketika menemukan buku duplikat untuk dimuat, tetapi masih harus memuat setiap buku asli dan duplikat yang telah dicetak.

O(log N)pada dasarnya berarti waktu naik secara linear sedangkan nnaik secara eksponensial. Jadi, jika diperlukan 1detik untuk menghitung 10elemen, dibutuhkan 2detik untuk menghitung 100elemen, 3detik untuk menghitung 1000elemen, dan sebagainya.

Itu adalah O(log n)ketika kita membagi dan menaklukkan jenis algoritma misalnya pencarian biner. Contoh lain adalah penyortiran cepat di mana setiap kali kita membagi array menjadi dua bagian dan setiap kali dibutuhkan O(N)waktu untuk menemukan elemen pivot. Karena itu N O(log N)

Banyak jawaban yang baik telah diposting untuk pertanyaan ini, tetapi saya percaya kita benar-benar kehilangan 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 berisi dua kali lipat jumlah node dibandingkan dengan level di atas (maka biner ):

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

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

Memplot log(n)pada selembar kertas biasa, akan menghasilkan grafik di mana kenaikan kurva melambat dengan nmeningkatnya:

Penjelasan di bawah ini menggunakan kasus pohon biner seimbang 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:

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

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

Gambaran

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 berbagai kategori algoritma.

Pertama, Anda ingin memiliki gagasan umum tentang Logaritma, yang dapat Anda peroleh dari https://en.wikipedia.org/wiki/Logarithm . Penggunaan ilmu alam edan log alami. Murid teknik akan menggunakan log_10 (log base 10) dan ilmuwan komputer akan menggunakan log_2 (log base 2) banyak, karena komputer berbasis biner. Kadang-kadang Anda akan melihat singkatan log natural sebagai ln(), insinyur biasanya meninggalkan _10 off dan hanya menggunakan log()dan log_2 disingkat 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, kemudian lihat yang lain. Saya telah menyertakan 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 lama daripada yang lain. Kategori-kategori ini membantu memberi kami cara memesan kinerja algoritma. Beberapa tumbuh lebih cepat seiring input n tumbuh. Tabel berikut menunjukkan pertumbuhan kata secara numerik. Dalam tabel di bawah ini anggap log (n) sebagai langit-langit log_2.

Contoh Kode Sederhana Dari Berbagai Kategori O Besar:

O (1) - Contoh Waktu Konstan:

• Algoritma 1:

Algoritma 1 mencetak halo sekali dan itu tidak bergantung pada n, jadi itu akan selalu berjalan dalam waktu yang konstan, begitu juga O(1).

print "hello";

• Algoritma 2:

Algoritma 2 mencetak halo 3 kali, namun tidak tergantung pada ukuran input. Bahkan ketika n tumbuh, algoritma ini hanya akan selalu mencetak halo 3 kali. Yang sedang dikatakan 3, adalah konstan, jadi algoritma ini juga O(1).

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

O (log (n)) - Contoh Logaritmik:

• Algoritma 3 - Ini bertindak seperti "log_2"

Algoritma 3 menunjukkan algoritma yang berjalan di log_2 (n). Perhatikan operasi posting dari for loop mengalikan nilai i saat ini dengan 2, jadi ilanjutkan dari 1 menjadi 2 menjadi 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. Pemberitahuan iberlaku dari 1 hingga 3 menjadi 9 hingga 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• Algoritma 5 - Ini bertindak seperti "log_1.02"

Algoritma 5 penting, karena membantu menunjukkan bahwa selama angkanya lebih besar dari 1 dan hasilnya berulang kali dikalikan dengan dirinya sendiri, bahwa Anda melihat algoritma logaritmik.

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

Pikirkan ini sebagai kombinasi dari O(log(n))dan O(n). Bersarang loop for membantu kami mendapatkanO(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 seperti algoritma 8, tetapi masing-masing loop 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 standar bersarang 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.

Jika Anda memiliki fungsi yang dibutuhkan:

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.

Kemudian dibutuhkan log ₂ (n) waktu. The Big O notasi , longgar berbicara, berarti bahwa hubungan hanya perlu benar untuk n besar, dan bahwa faktor konstan dan istilah yang lebih kecil dapat diabaikan.

Logarithmic running time ( O(log n)) pada dasarnya berarti bahwa waktu berjalan tumbuh sebanding dengan logaritma ukuran input - sebagai contoh, jika 10 item paling banyak memakan waktu x, dan 100 item paling banyak, katakanlah 2x, dan 10.000 item membutuhkan paling banyak 4x, maka itu tampak seperti O(log n)kompleksitas waktu.

Logaritma

Ok, mari kita coba dan memahami sepenuhnya apa sebenarnya logaritma itu.

Bayangkan kita memiliki tali dan kita mengikatnya pada seekor kuda. Jika tali langsung diikat ke kuda, kekuatan yang kuda perlu tarik (katakanlah, dari seorang pria) secara langsung 1.

Sekarang bayangkan talinya melingkari sebuah tiang. Kuda untuk melarikan diri sekarang harus menarik berkali-kali lebih keras. Jumlah kali akan tergantung pada kekasaran tali dan ukuran tiang, tetapi mari kita asumsikan itu akan melipatgandakan kekuatan seseorang dengan 10 (ketika tali membuat putaran penuh).

Sekarang jika talinya dililitkan sekali, kuda harus menarik 10 kali lebih keras. Jika manusia memutuskan untuk membuat kuda itu sangat sulit, ia dapat mengikat tali lagi di sekeliling tiang, menambah kekuatannya dengan tambahan 10 kali. Loop ketiga akan kembali meningkatkan kekuatan dengan 10 kali lebih jauh.

Kita dapat melihat bahwa untuk setiap loop, nilainya meningkat sebesar 10. Jumlah putaran yang diperlukan untuk mendapatkan angka apa pun disebut logaritma angka yaitu kita perlu 3 posting untuk menggandakan kekuatan Anda dengan 1000 kali, 6 posting untuk menggandakan kekuatan Anda dengan 1.000.000.

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

Jadi, apa sebenarnya yang dimaksud dengan O (log n)?

Dalam contoh kami di atas, 'tingkat pertumbuhan' kami adalah O (log n) . Untuk setiap loop tambahan, gaya yang dapat ditanggung tali kami adalah 10 kali lebih besar:

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 Anda butuh 7 tebakan untuk memperbaiki ini. Tapi apa hubungannya di sini? Berapakah 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 kita memiliki 128 angka, kita juga bisa menebak angka dalam 7 percobaan tetapi 129 angka akan membawa kita paling banyak 8 upaya (dalam kaitannya dengan logaritma, di sini kita akan membutuhkan 7 tebakan untuk rentang nilai 128, 10 tebakan untuk kisaran nilai 1024 7 adalah logaritma 128, 10 adalah logaritma 1024 (basis 2)).

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

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

Bagaimana dengan O (n log n)?

Anda pada akhirnya akan menemukan algoritma waktu O (n log (n)) linearitmik . Aturan praktis di atas berlaku lagi, tetapi kali ini fungsi logaritmik 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 berulang melalui daftar (O (n)). Kemudian lihat apakah ada lingkaran dalam. Jika loop dalam memotong / mengurangi set data pada setiap iterasi, loop itu adalah (O (log n)), dan algoritma keseluruhan adalah = O (n log n) .

Penafian: Contoh tali-logaritma diambil dari buku Delight karya matematikawan karya W.Sawyer .

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

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

Jika suatu operasi membuat serangkaian keputusan waktu konstan yang masing-masing dibagi dua (dikurangi 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 ...) dengan ukuran N dari input, bukannya O (N).

Dan seterusnya.

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

Jika Anda menambah ukuran masalah dengan jumlah multiplikatif (yaitu, gandakan ukurannya dengan 10), pekerjaan hanya bertambah dengan jumlah aditif.

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

Pertama, saya sarankan Anda membaca buku berikut;

Algoritma (Edisi ke-4)

Berikut adalah beberapa fungsi dan kerumitan yang diharapkan. Angka menunjukkan frekuensi eksekusi pernyataan .

Mengikuti Big-O Complexity Chart juga diambil dari bigocheatsheet

Terakhir showcase sangat sederhana ada menunjukkan bagaimana itu dihitung;

Anatomi dari frekuensi eksekusi pernyataan program.

Menganalisis waktu berjalan suatu program (contoh).

Apa log _b (n)?

Ini adalah berapa kali Anda dapat memotong log dengan panjang n berulang kali menjadi b bagian yang sama sebelum mencapai bagian ukuran 1.

Algoritma Divide and Conquer biasanya memiliki lognkomponen untuk waktu yang berjalan. Ini berasal dari separuh berulang input.

Dalam kasus pencarian biner, setiap iterasi Anda membuang setengah dari input. Perlu dicatat bahwa dalam notasi Big-O, log adalah log basis 2.

Sunting: Seperti dicatat, basis log tidak masalah, tetapi ketika menurunkan kinerja Big-O suatu algoritma, faktor log akan datang dari separuh, maka mengapa saya menganggapnya sebagai basis 2.

Tapi apa sebenarnya O (log n)? Sebagai contoh, apa artinya mengatakan bahwa ketinggian pohon biner> lengkap adalah O (log n)?

Saya akan mengulangi ini sebagai 'tinggi pohon biner lengkap adalah log n'. Menggambarkan ketinggian pohon biner lengkap akan menjadi O (log n), jika Anda melintasi langkah demi langkah.

Saya tidak mengerti bagaimana mengidentifikasi suatu fungsi dengan waktu logaritmik.

Logaritma pada dasarnya adalah kebalikan dari eksponensial. Jadi, jika setiap 'langkah' dari fungsi Anda menghilangkan faktor elemen dari set item asli, itu adalah algoritma waktu logaritmik.

Sebagai contoh pohon, Anda dapat dengan mudah melihat bahwa mengecilkan tingkat node mengurangi jumlah elemen eksponensial saat Anda terus melintasi. Contoh populer dari melihat-lihat buku telepon yang diurutkan pada dasarnya setara dengan menelusuri pohon pencarian biner (halaman tengah adalah elemen root, dan Anda dapat menyimpulkan pada setiap langkah apakah ke kiri atau kanan).

2 kasus ini akan memakan waktu O (log n)

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) agak menyesatkan, lebih tepatnya itu O (log ₂ n), yaitu (logaritma dengan basis 2).

Ketinggian pohon biner seimbang adalah O (log ₂ n), karena setiap node memiliki dua (catat "dua" seperti dalam log ₂ n) simpul anak. Jadi, pohon dengan n node memiliki tinggi log ₂ n.

Contoh lain adalah pencarian biner, yang memiliki waktu berjalan O (log ₂ n) karena pada setiap langkah Anda membagi ruang pencarian dengan 2.

O(log n) mengacu pada fungsi (atau algoritma, atau langkah dalam algoritma) yang bekerja dalam jumlah waktu yang sebanding dengan logaritma (biasanya basis 2 dalam kebanyakan kasus, tetapi tidak selalu, dan dalam hal apa pun ini tidak signifikan dengan notasi O-besar *) dari ukuran input.

Fungsi logaritmik adalah kebalikan dari fungsi eksponensial. Dengan kata lain, jika input Anda tumbuh secara eksponensial (bukan linear, seperti yang biasanya Anda pertimbangkan), fungsi Anda tumbuh secara linear.

O(log n)waktu berlari sangat umum dalam segala jenis aplikasi divide-and-menaklukkan, karena Anda (idealnya) memotong pekerjaan menjadi dua setiap kali. Jika dalam setiap langkah divisi atau taklukkan, Anda melakukan pekerjaan waktu konstan (atau pekerjaan yang bukan waktu konstan, tetapi dengan waktu tumbuh lebih lambat daripada O(log n)), maka seluruh fungsi Anda O(log n). Ini cukup umum untuk setiap langkah membutuhkan waktu linier pada input sebagai gantinya; ini akan berjumlah total kompleksitas waktu O(n log n).

Kompleksitas waktu berjalan dari pencarian biner adalah contoh dari O(log n). Ini karena dalam pencarian biner, Anda selalu mengabaikan setengah dari input Anda di setiap langkah selanjutnya dengan membagi array menjadi setengah dan hanya fokus pada setengahnya dengan setiap langkah. Setiap langkah adalah waktu yang konstan, karena dalam pencarian biner Anda hanya perlu membandingkan satu elemen dengan kunci Anda untuk mengetahui apa yang harus dilakukan selanjutnya terlepas dari seberapa besar array yang Anda pertimbangkan ada di titik mana pun. Jadi Anda melakukan kira-kira langkah (n) / log (2) langkah.

Kompleksitas waktu berjalan dari semacam gabungan adalah contoh dari O(n log n). Ini karena Anda membagi array menjadi dua dengan setiap langkah, menghasilkan total kira-kira langkah-langkah log (n) / log (2). Namun, dalam setiap langkah Anda perlu melakukan operasi penggabungan pada semua elemen (apakah itu satu operasi penggabungan pada dua sublists dari elemen n / 2, atau dua operasi penggabungan pada empat sublist dari elemen n / 4, tidak relevan karena menambah keharusan untuk lakukan ini untuk n elemen di setiap langkah). Dengan demikian, kompleksitas totalnya adalah O(n log n).

* Ingat bahwa notasi O besar, menurut definisi , konstanta tidak masalah. Juga oleh perubahan aturan dasar untuk logaritma, satu-satunya perbedaan antara logaritma dari basis yang berbeda adalah faktor konstan.

Ini berarti bahwa waktu yang dibutuhkan untuk tugas ini bertambah dengan log (n) (contoh: 2s untuk n = 10, 4s untuk n = 100, ...). Baca artikel Wikipedia tentang Algoritma Binary Search dan Notasi O Besar untuk lebih banyak precision

Sederhananya: Pada setiap langkah algoritma Anda, Anda dapat memotong pekerjaan menjadi dua. (Asimptotik setara dengan ketiga, keempat, ...)

Jika Anda memplot fungsi logaritmik pada kalkulator grafis atau yang serupa, Anda akan melihatnya naik sangat lambat - bahkan lebih lambat dari fungsi linear.

Inilah sebabnya mengapa algoritma dengan kompleksitas waktu logaritmik sangat dicari: bahkan untuk n yang sangat besar (misalkan n = 10 ^ 8, misalnya), mereka melakukan lebih dari yang dapat diterima.

Tapi apa sebenarnya O (log n)

Apa artinya tepatnya adalah "sebagai nkecenderungan ke arah infinity, timekecenderungan ke arah a*log(n)mana aadalah faktor penskalaan konstan".

Atau sebenarnya, itu tidak berarti bahwa; lebih mungkin itu berarti sesuatu seperti " timedibagi oleh a*log(n)kecenderungan ke arah 1".

"Cenderung ke arah" memiliki arti matematika biasa dari 'analisis': "jika Anda memilih misalnya, bahwa setiap sewenang-wenang kecil non-nol konstan k, maka saya dapat menemukan yang sesuai nilai Xsehingga ((time/(a*log(n))) - 1)kurang dari kuntuk semua nilai nlebih besar dari X."

Dalam istilah awam, ini berarti bahwa persamaan untuk waktu mungkin memiliki beberapa komponen lain: misalnya, ia mungkin memiliki waktu startup yang konstan; tetapi komponen-komponen lain ini pucat menuju tidak penting untuk nilai besar n, dan a * log (n) adalah istilah yang mendominasi untuk n besar.

Perhatikan bahwa jika persamaannya adalah, misalnya ...

waktu (n) = a + b log (n) + c n + d n n

... maka ini akan menjadi O (n kuadrat) karena, tidak peduli apa nilai konstanta a, b, c, dan non-nol d, d*n*nistilah tersebut akan selalu mendominasi yang lain untuk nilai n yang cukup besar.

Itulah yang dimaksud dengan sedikit notasi O: artinya "apa urutan istilah dominan untuk n yang cukup besar".

Saya dapat menambahkan sesuatu yang menarik, yang saya baca di buku oleh Kormen dan lain-lain sejak lama. Sekarang, bayangkan sebuah masalah, di mana kita harus menemukan solusi di ruang masalah. Ruang masalah ini harus terbatas.

Sekarang, jika Anda dapat membuktikan, bahwa pada setiap iterasi dari algoritma Anda Anda memotong sebagian kecil dari ruang ini, yang tidak kurang dari batas tertentu, ini berarti bahwa algoritma Anda berjalan dalam waktu O (logN).

Saya harus menunjukkan, bahwa kita berbicara di sini tentang batas fraksi relatif, bukan batas absolut. Pencarian biner adalah contoh klasik. Pada setiap langkah kita membuang 1/2 dari ruang masalah. Tetapi pencarian biner bukan satu-satunya contoh. Misalkan, Anda membuktikan entah bagaimana, bahwa pada setiap langkah Anda membuang setidaknya 1/128 ruang masalah. Itu berarti, program Anda masih berjalan pada waktu O (logN), meskipun secara signifikan lebih lambat daripada pencarian biner. Ini adalah petunjuk yang sangat baik dalam menganalisis algoritma rekursif. Seringkali dapat dibuktikan bahwa pada setiap langkah rekursi tidak akan menggunakan beberapa varian, dan ini mengarah pada pemutusan sebagian fraksi dalam ruang masalah.

Saya dapat memberikan contoh untuk for for dan mungkin sekali memahami konsep mungkin akan lebih mudah untuk dipahami dalam konteks yang berbeda.

Itu berarti bahwa dalam loop langkahnya tumbuh secara eksponensial. Misalnya

for (i=1; i<=n; i=i*2) {;}

Kompleksitas dalam notasi-O dari program ini adalah O (log (n)). Mari kita coba memutarnya dengan tangan (ada di antara 512 dan 1023 (tidak termasuk 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Meskipun n berada di suatu tempat antara 512 dan 1023, hanya 10 iterasi yang terjadi. Ini karena langkah dalam loop tumbuh secara eksponensial dan dengan demikian hanya membutuhkan 10 iterasi untuk mencapai terminasi.

Logaritma x (ke dasar a) adalah fungsi kebalikan dari a ^ x.

Itu seperti mengatakan bahwa logaritma adalah kebalikan dari eksponensial.

Sekarang coba lihat seperti itu, jika eksponensial tumbuh sangat cepat maka logaritma tumbuh (berbanding terbalik) sangat lambat.

Perbedaan antara O (n) dan O (log (n)) sangat besar, mirip dengan perbedaan antara O (n) dan O (a ^ n) (menjadi konstan).

Sebenarnya, jika Anda memiliki daftar elemen n, dan membuat pohon biner dari daftar itu (seperti dalam algoritma divide and conquer), Anda akan terus membaginya dengan 2 hingga Anda mencapai daftar ukuran 1 (daun).

Pada langkah pertama, Anda membagi 2. Anda kemudian memiliki 2 daftar (2 ^ 1), Anda membagi masing-masing dengan 2, sehingga Anda memiliki 4 daftar (2 ^ 2), Anda membagi lagi, Anda memiliki 8 daftar (2 ^ 3 ) dan seterusnya hingga ukuran daftar Anda adalah 1

Itu memberi Anda persamaan:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(Anda mengambil lg dari setiap sisi, lg menjadi basis log 2)

Setiap kali kami menulis algoritma atau kode, kami mencoba menganalisis kompleksitas asimptotiknya. Ini berbeda dari kompleksitas waktunya .

Kompleksitas asimptotik adalah perilaku waktu eksekusi suatu algoritma sedangkan kompleksitas waktu adalah waktu eksekusi aktual. Tetapi beberapa orang menggunakan istilah ini secara bergantian.

Karena kompleksitas waktu tergantung pada berbagai parameter yaitu.
1. Sistem Fisik
2. Bahasa Pemrograman
3. Gaya pengkodean
4. Dan banyak lagi ......

Waktu eksekusi aktual bukan ukuran yang baik untuk analisis.

Sebagai gantinya kami mengambil ukuran input sebagai parameter karena apa pun kodenya, inputnya sama. Jadi waktu eksekusi adalah fungsi dari ukuran input.

Berikut ini adalah contoh Algoritma Linear Waktu

Pencarian Linear
Diberi n elemen input, untuk mencari elemen dalam array yang paling Anda butuhkan perbandingan 'n' . Dengan kata lain, tidak peduli apa bahasa pemrograman yang Anda gunakan, gaya pengkodean apa yang Anda sukai, pada sistem apa Anda menjalankannya. Dalam skenario terburuk, ini hanya membutuhkan perbandingan n. Waktu eksekusi berbanding lurus dengan ukuran input.

Dan itu bukan hanya pencarian, apa pun pekerjaan (kenaikan, perbandingan, atau operasi apa pun) yang merupakan fungsi dari ukuran input.

Jadi ketika Anda mengatakan algoritma apa pun adalah O (log n) itu berarti waktu eksekusi adalah log kali ukuran input n.

Ketika ukuran input meningkatkan pekerjaan yang dilakukan (di sini waktu eksekusi) meningkat. (Oleh karena itu proporsionalitas)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Lihat sebagai ukuran input meningkat pekerjaan yang dilakukan meningkat dan tidak tergantung pada mesin apa pun. Dan jika Anda mencoba mencari tahu nilai unit kerja itu sebenarnya tergantung pada parameter yang ditentukan di atas. Ini akan berubah sesuai dengan sistem dan semua.

log x to base b = y adalah kebalikan dari b^y = x

Jika Anda memiliki pohon M-ary dengan kedalaman d dan ukuran n, maka:

• melintasi seluruh pohon ~ O (M ^ d) = O (n)

• Berjalan satu jalur di pohon ~ O (d) = O (log n ke basis M)

Dalam teknologi informasi itu berarti:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Semut tampaknya notasi ini sebagian besar diambil dari matematika.

Dalam artikel ini ada kutipan: DE Knuth, "OMICRON BESAR DAN OMEGA BESAR DAN THETA BESAR", 1976 :

Atas dasar masalah yang dibahas di sini, saya mengusulkan agar anggota SIGACT, dan editor jurnal ilmu komputer dan matematika, mengadopsi notasi sebagaimana didefinisikan di atas, kecuali jika alternatif yang lebih baik dapat ditemukan dengan segera .

Hari ini adalah 2016, tetapi kami masih menggunakannya sampai sekarang.

Dalam analisis matematika itu berarti:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Tetapi bahkan dalam analisis matematika kadang-kadang simbol ini digunakan dalam arti "C * g (n)> f (n)> 0".

Seperti yang saya tahu dari universitas, simbol diperkenalkan oleh ahli matematika Jerman Landau (1877-1938)

Contoh biner lengkap adalah O (ln n) karena pencarian terlihat seperti ini:

1 2 3 4 5 6 7 8 9 10 11 12

Mencari 4 menghasilkan 3 hit: 6, 3 lalu 4. Dan log2 12 = 3, yang merupakan apporximate bagus untuk berapa banyak hit di mana diperlukan.

Jika Anda mencari jawaban berdasarkan intuisi, saya ingin memberikan dua interpretasi untuk Anda.

1. Bayangkan sebuah bukit yang sangat tinggi dengan basis yang sangat luas pula. Untuk mencapai puncak bukit ada dua cara: satu adalah jalur khusus yang berputar secara spiral di sekitar bukit mencapai di atas, yang lain: teras kecil seperti ukiran dipotong untuk menyediakan tangga. Sekarang jika cara pertama mencapai waktu linear O (n), yang kedua adalah O (log n).

2. Bayangkan sebuah algoritma, yang menerima integer, nsebagai input dan melengkapi dalam waktu yang proporsional untuk nkemudian itu adalah O (n) atau theta (n) tetapi jika itu berjalan dalam proporsi waktu ke number of digits or the number of bits in the binary representation on numbermaka algoritma berjalan di O (log n) atau theta (log n) waktu.

Algoritma dalam paradigma Divide and Conquer adalah kompleksitas O (logn). Satu contoh di sini, hitung fungsi daya Anda sendiri,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

dari http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/