Logaritma biner: Perbedaan antara revisi

'''Logaritma biner''' ({{lang-en|binary logarithm}}) dalam [[matematika]] adalah, adalah [[logaritma]] dengan [[Sistem bilangan biner|basis 2]], yang biasanya dilambangkan dengan '''log<submath>2\log_2 n</submath>&nbsp;''n''''' atau '''<supmath>^2\!\log n</supmath>log&nbsp;''n'''''. Logaritma biner merupakan [[fungsi invers]] dari [[fungsi kuadrat|fungsi kuadrat atau fungsi pangkat dua]]. LogaritmeLogaritma biner ''<math>n''</math> adalah kepangkatan bilangan [[2 (angka)|dua]] untuk mendapatkan nilai &nbsp;''<math>n''</math>. Jadi:

Misalnya logaritma biner 1 adalah 0, logaritma biner 2 adalah 1, logaritma biner 4 adalah 2, logaritma biner 8 adalah 3, logaritma biner 16 adalah 4, logaritma biner 32 adalah &nbsp;5 dan seterusnya.

[[Berkas:Leonhard_Euler.jpg|jmpl|180px|[[Leonhard Euler]] adalah orang pertama yang menerapkan logaritmelogaritma biner pada [[teori musik]], pada tahun 1739.]]

Dalam matematika, logaritma biner suatu bilangan ''n'' ditulis sebagai log<submath>2\log_2 n</submath>&nbsp;''n'' atau <supmath>^2\!\log n</supmath>log&nbsp;''n''. Namun, sejumlah notasi lain fungsi ini telah diusulkan dan digunakan dalam berbagai bidang.

Sejumlah pengarang menuliskan logaritmelogaritma biner sebagai '''<math>\lg ''n''''' </math>.<ref name="clrs">{{Introduction to Algorithms|pages=34, 53–54|edition=2}}</ref><ref name="sw11">{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin Daniel|last2=Wayne|publisher=Addison-Wesley Professional|year=2011|isbn=9780321573513|page=185|url=http://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA185}}.</ref> [[Donald Knuth]] mengungkapkan bahwa notasi ini didapatnya dari usulan [[Edward Reingold]],<ref name="knuth">{{citation|title=[[The Art of Computer Programming]], Volume 1: Fundamental Algorithms|first=Donald E.|last=Knuth|authorlink=Donald Knuth|edition=3rd|publisher=Addison-Wesley Professional|year=1997|isbn=9780321635747}}, [http://books.google.com/books?id=x9AsAwAAQBAJ&pg=PA11 p.&nbsp;11]. The same notation was in the 1973 2nd edition of the same book (p.&nbsp;23) but without the credit to Reingold.</ref> tetapi penggunaannya dalam teori informasi maupun ilmu komputer tampaknya sudah ada sebelum Reingold aktif.<ref>{{citation

| year = 1962}}.</ref> LogaritmeLogaritma biner juga pernah ditulis sebagai '''<math>\log ''n''</math>''', dengan catatan bahwa basis default logaritma adalah bilangan 2 (bukan 10 sebagaimana lazimnya).<ref>{{citation|title=Mathematics for Engineers|first1=Georges|last1=Fiche|first2=Gerard|last2=Hebuterne|publisher=John Wiley & Sons|year=2013|isbn=9781118623336|page=152|url=http://books.google.com/books?id=TqkckiuuXg8C&pg=PT152|quote=In the following, and unless otherwise stated, the notation log ''x'' always stands for the logarithm to the base 2 of ''x''}}.</ref><ref>{{citation|title=Elements of Information Theory|first1=Thomas M.|last1=Cover|first2=Joy A.|last2=Thomas|edition=2nd|publisher=John Wiley & Sons|year=2012|isbn=9781118585771|page=33|url=http://books.google.com/books?id=VWq5GG6ycxMC&pg=PT33|quote=Unless otherwise specified, we will take all logarithms to base 2}}.</ref><ref name="gt02">{{citation|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithm Design: Foundations, Analysis, and Internet Examples|publisher=John Wiley & Sons|year=2002|page=23|quote=One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the base ''b'' of the logarithm when ''b''&nbsp;=&nbsp;2.}}</ref>

Notasi lain yang terkadang digunakan untuk fungsi tersebut (terutama dalam [[bahasa Jerman]]) adalah '''<math>\operatorname{ld} ''n'''''</math>, dari frasa [[bahasa Latin]] ''[[wikt:logarithmus#bahasa Latin|logarithmus]] [[wikt:dualis#bahasa Latin|duālis]]''.<ref>For instance, see {{citation|title=Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum|first=Friedrich L.|last=Bauer|publisher=Springer Science & Business Media|year=2009|isbn=9783642029929|page=54|url=http://books.google.com/books?id=y4uTaLiN-wQC&pg=PA54}}.</ref> Spesifikasi [[ISO 31-11]] dan [[ISO 80000-2]] menyarankan notasi lainnya, '''<math>\operatorname{lb} ''n'''''</math>; dalam spesifikasi ini, <math>\lg ''n'' </math> digunakan untuk log<submath>\log_{10} n</submath> ''n''.<ref>For DIN 1302 see {{citation

Banyak digit ([[bit]]) dalam [[representasi biner]] sebuah bilangan bulat positif ''<math>n''</math> adalah [[Fungsi lantai dan atap|bagian bulat]] dari <math>1&nbsp; +&nbsp;log<sub>2 \log_2 n</submath>&nbsp;''n'', i.e.yakni<ref name="sw11"/>

Meskipun [[logaritma alami]] lebih penting daripada logaritma biner dalam banyak bidang matematika murni seperti [[teori bilangan]] dan [[analisis matematis]], logaritma biner memiliki beberapa penerapan dalam [[kombinatorikskombinatorik]]:

*Semua [[binarypohon treebiner]] dengan ''<math>n''</math> daun memiliki tinggi paling tidak sebesar <math>\log_2 n</math>, dengan nilainya sama persisi apabila ''<math>n''</math> merupakan [[perpangkatan dari dua]] dan pohonnya merupakan [[pohon biner lengkap]].<ref>{{citation

*Semua [[keluarga himpunan]] dengan ''<math>n''</math> himpunan berbeda memiliki paling tidak <math>\log_2 n</math> anggota dalam gabungannya, dengan nilainya sama persis apabila keluarga tersebut merupakan sebuah [[himpunan kuasa]].<ref>Ekuivalennya, sebuah keluarga dengan ''k'' anggota berbeda punya maksimal 2^''k'' himpunan berbeda, dengan nilainya sama persis apabila keluarganya merupakan himpunan kuasa.</ref><!--

Logaritma biner juga sering muncul dalam [[analisis algoritma]],<ref name="gt02"/> bukan hanya karena aritmetika bilangan biner kerap digunakan dalam algoritma, tetapi juga karena logaritma biner muncul dalam analisis algoritma yang menggunakan percabangan dua arah.<ref name="knuth"/> Jika suatu masalah awalnya punya ''<math>n</math>'' pilihan untuk dipilih, dan setiap pengulangan algoritma membagi dua banyak pilihannya, maka banyak pengulangan yang diperlukan untuk mendapatkan satu pilihan adalah bagian bulat dari log<submath>2\log_2 n</submath>&nbsp;''n''. Ide ini digunakan dalam menganalisis beberapa [[algoritma]] dan [[struktur data]]. Contohnya, dalam [[pencarian biner]], ukuran masalah dibagi dua pada setiap pengulangannya, sehingga perlu kira-kira log<submath>2\log_2 n</submath>''n'' pengulangan untuk mendapatkan masalah berukuran 1, yang bisa diselesaikan dalam waktu konstan. Tidak jauh berbeda, [[pohon pencarian biner]] yang seimbang dan memiliki ''n'' element pasti punya tinggi log<submath>2\log_2 n + 1</submath>&nbsp;''n''&nbsp;+&nbsp;1.

Namun, lama waktu dijalankannya algoritma biasanya diekspresikan dalam [[notasi O besar]], yang mengabaikan faktor konstanta. Karena log<sub>2</submath>\log_2 ''n'' = (log<sub>''k''\frac{\log_k n}{\log_k 2}</submath>&nbsp;''n'')/(log, dengan <submath>''k''</submath>&nbsp;2), dengan ''k'' adalah angkasuatu apapunbilangan yang lebih dari 1, algoritma yang berjalan dalam waktu ''<math>O''(log<sub>2\log_2 n)</submath>&nbsp;''n'') bisa juga dikatakan berjalan dalam waktu ''O''(log<submath>O(\log_{13} n)</submath>&nbsp;''n''). Jadi basis logaritma dalam ekspresi-ekspresi seperti ''<math>O''(\log&nbsp;'' n'')</math> atau ''<math>O''(''n''&nbsp; \log&nbsp;'' n'')</math> tidaklah penting.<ref name="clrs"/> Akan tetapi, dalam beberapa konteks, basis logaritma perlu dijelaskan. Contohnya <math>O(2^{\log_2 n})</math> tidak sama dengan <math>O(2^{\ln n})</math> karena yang pertama sama dengan <math>O(n)</math> sedangkan yang kedua sama dengan <math>O(n^{0.6931\dots})</math>.

Algoritma dengan waktu jalan ''<math>O''(''n''&nbsp; \log&nbsp;'' n'')</math> terkadang disebut ''linearitmik''.<ref>{{harvtxt|Sedgewick|Wayne|2011}}, [http://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA186 p.&nbsp;186].</ref> Contoh algoritma dengan waktu jalan ''<math>O''(\log&nbsp;'' n'')</math> atau ''<math>O''(''n''&nbsp; \log&nbsp;'' n'')</math> di antaranya:

Dalam analisis data [[mikrolarik]] dalam [[bioinformatika]], tingkat ekspresi gen biasanya dibandingkan dengan menggunakan logaritma biner dari rasio tingkat ekspresi. Dengan menggunakan logaritma basis&nbsp; 2, tingkat ekspresi yang menjadi dua kali lipat bisa digambarkan dengan rasio <math>\log 1</math>, tingkat ekspresi yang menjadi setengah bisa digambarkan dengan log rasio −1, dan tingkat ekspresi yang tidak berubah bisa digambarkan dengan rasio log nol, sebagai contoh.<ref>{{citation|title=Microarray Gene Expression Data Analysis: A Beginner's Guide|first1=Helen|last1=Causton|first2=John|last2=Quackenbush|first3=Alvis|last3=Brazma|publisher=John Wiley & Sons|year=2009|isbn=9781444311563|pages=49–50|url=http://books.google.com/books?id=bg6D_7mdG70C&pg=PA49}}.</ref> Titik-titik data yang didapatkan dengan cara ini biasanya divisualisasikan sebagai sebuah [[diagram pencar]] di mana salah satu atau kedua sumbu koordinatnya adalah logaritma biner dari rasio intensitas, atau dalam visualisasi seperti [[diagram MA]] dan [[diagram RA]] yang memutar dan menskalakan rasio log dari diagram pencarnya.<ref>{{citation|title=Computational and Statistical Methods for Protein Quantification by Mass Spectrometry|first1=Ingvar|last1=Eidhammer|first2=Harald|last2=Barsnes|first3=Geir Egil|last3=Eide|first4=Lennart|last4=Martens|publisher=John Wiley & Sons|year=2012|isbn=9781118493786|page=105|url=http://books.google.com/books?id=3Z3VbhLz6pMC&pg=PA105}}.</ref>

Dalam [[teori musik]], [[Interval (musik)|interval]] atau perbedaan dalam persepsi antara dua nada ditentukan oleh rasio kedua [[frekuensi]]nya. Interval yang datang dari rasio [[bilangan rasional]] dengan pembilang dan penyebut kecil pada khususnya dianggap merdu. Interval yang paling sederhana dan paling penting adalah [[oktaf]], suatu rasio frekuensi <math>2:1</math>. Bilangan oktaf dari perbedaan dua nada merupakan logaritma biner dari rasio frekuensi kedua nada itu.<ref name="mga">{{citation|title=The Musician's Guide to Acoustics|first1=Murray|last1=Campbell|first2=Clive|last2=Greated|publisher=Oxford University Press|year=1994|isbn=9780191591679|page=78|url=http://books.google.com/books?id=iiCZwwFG0x0C&pg=PA78}}.</ref>

Untuk mempelajari [[sistem penalaan]] dan aspek lain dari teori musik dibutuhkan pembedaan yang lebih peka antara nada-nada, sehingga diperlukan suatu pengukuran besarnya interval yang lebih halus dari suatu oktaf dan dapat ditambah (sebagaimana suatu [[logaritma]]) bukannya dikalikan (sebagaimana rasio frekuensi). Jadi, jika nada-nada ''<math>x''</math>, ''<math>y''</math>, dan ''<math>z''</math> membentuk urutan nada-nada yang menaik, maka ukuran interval dari ''<math>x''</math> ke ''<math>y''</math> ditambah ukuran interval dari ''<math>y''</math> ke ''<math>z''</math> seharusnya sama dengan ukuran interval dari ''<math>x</math>'' ke ''<math>z''</math>. Pengukuran semacam ini dilakukan dengan satuan [[Sen (musik)|sen]], yang membagi suatu oktaf menjadi 1200 interval yang sama (12 [[semitone]] yang masing-masing terdiri dari 100 ''cent''). Secara matematis, nada-nada dengan frekuensi ''f''<submath>1f_1</submath> dan ''f''<submath>2f_2</submath>, mempunyai jumlah sen dalam interval dari ''<math>x''</math> ke ''<math>y''</math> sebesar<ref name="mga"/>

Fungsi <code>log2</code> dimasukkan ke dalam [[:En:C mathematical functions|fungsi matematika C]] standar. Versi default fungsi ini mengambil argumen [[double precision|''double precision'']] tetapi varian-variannya mengizinkan argumen dalam bentuk ''single-precision'' atau sebagai [[long double|''long double'']].<ref>{{citation | url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf | title=ISO/IEC 9899:1999 specification | page=226| contribution = 7.12.6.10 The log2 functions }}.</ref>