Двійковий логарифм

Кількість розрядів (біт) в двійковому представленні додатного цілого n дорівнюватиме цілій частині числа 1 + log₂n.[10]

${\displaystyle \lfloor \log _{2}n\rfloor +1.\,}$

В теорії інформації, визначення кількості власної інформації та інформаційна ентропія часто задаються за допомогою двійкового логарифму, тим самим представляючи біт як фундаментальну одиницю інформації. Однак, в альтернативних представленнях цих визначень також використовують натуральний логарифм і нат.[11]

Хоча натуральний логарифм є більш важливим ніж двійковий логарифм для багатьох галузей чистої математики, таких як теорія чисел і математичний аналіз,[12] двійковий логарифм має ряд застосувань в комбінаториці:

• Кожне двійкове дерево кожне n листя має висоту принаймні в log₂n, і стає рівним цьому значенню, коли n є степенем двійки, а саме дерево є повним двійковим деревом.[13] Відповідно, число Стрехлера річкової системи із n притоками буде щонайбільше дорівнювати log₂n + 1.[14]
• Кожне сімейство множин з n різними наборами має принаймні log₂n елементів в купі, і буде рівністю коли це сімейство становить булеан.[15]
• Кожен частковий куб із n вершинами має ізометричну розмірність щонайменше в log₂n, і має не більше ніж 12 n log₂n ребер, при чому рівність буде, якщо частковий куб є графом гіперкуба.[16]
• Відповідно до Теореми Рамсея, кожний неорієнтований граф з n-вершин має або кліку або незалежну множину з розміром в логарифмічній залежності із n. Точний розмір гарантовано не відомий, але найкраща відома межа цього розміру застосовує двійковий логарифм. Зокрема, всі графи мають кліку або незалежну множину розміром принаймні в 12 log₂n (1 − o(1)) і майже всі графи не мають кліки або незалежної множини більшого розміру ніж 2 log₂n (1 + o(1)).[17]
• Із теорії математичного аналізу модель Гільберта-Шеннона-Рідса для випадкового тасування кар, можна визначити число разів необхідних при тасуванні колоди з n-карт, використовуючи метод riffle shuffle, аби отримати кількість перестановок, що будуть близкі до рівномірного розподілу, і це значення приблизно дорівнює 32 log₂n. Цей підрахунок дав основу для рекомендації, що колода з 52-карт повинна перемішуватись сім разів.[18]

Двійковий пошук в відсортованому масиві, часова складність алгоритму розраховується за допомогою двійкових логарифмів

Двійковий логарифм також часто фігурує в аналізі алгоритмів, не тільки через часте використання двійкової арифметики в алгоритмах, а й тому, що двійкові логарифми зустрічаються при аналізі алгоритмів, заснованих на двонаправлених розгалуженнях.[19] Якщо задача початково має n варіантів шляху вирішення, а кожна ітерація алгоритму зменшує кількість варіантів в два рази, тоді кількість ітерацій, необхідних аби завершити пошук на одному з варіантів знову таки є цілою частиною від log₂n. Цей підхід використовується при аналізі багатьох алгоритмів і структур даних. Наприклад, при двійковому пошуку, об'єм задачі, що розв'язується змешнується навпіл при кожній ітерації, і таким чином приблизно log₂n ітерацій необхідно здійснити або отримати задачу розміром 1, що означає, що задачу можна вирішити за скінченний передбачений час.[20] Аналогічно, ідеально збалансоване дерево двійкового пошуку, яке містить n елементів має висоту log₂(n + 1) − 1.[21]

Час роботи алгоритму зазвичай виражають в нотації Ландау (велике О), яка використовується для спрощення виразів не указуючи постійних складових і членів нижчого порядку. Оскільки логарифми з різними основами відрізняються один від одного лише на сталу величину, про алгоритми, які виконуються за час O(log₂n) також можна казати, що вони виконуються за O(log₁₃ n) часу. Основу логарифму в виразах такого вигляду як O(log n) або O(n log n) можна не вказувати.[22][23] Однак, якщо логарифм вказується в показнику степеня при розрахунку часу, основою логарифму не можна нехтувати і треба вказувати. Наприклад, O(2^log₂n) не те саме, що O(2^{ln n}) оскільки останнє буде дорівнювати O(n) а перший вираз — O(n^0.6931...).

Алгоритми з часом виконання O(n log n) іноді називають лінійно-логарифмічними.[24] Прикладами алгоритмів із часом виконання O(log n) або O(n log n) є:

• Швидке сортування і інші алгоритми сортування порівняннями[25]
• Пошук в збалансованому двійковому дереві пошуку[26]
• Швидке піднесення до степеня[27]
• Задача пошуку найбільшої зростаючої підпослідовності[28]

В теорії музики, інтервал або різниця сприйняття між двома тонами визначається відношенням їх частот. Інтервали, що утворені за допомогою співвідношення раціональних чисел із малими чисельниками і знаменниками сприймаються особливо милозвучно. Найпростішим і найважливішим із таких інтервалів є октава, що має співвідношення частот 2:1. Кількість октав, на які відрізняються звукові тони дорівнюють двійковому логарифму від співвідношення їх частот.[29]

При вивченні музичного строю і інших аспектів музичної теорії, які потребують кращого розрізнення між тонами, ж зручним мати міру розміру інтервалу меншу за октаву із властивістю адитивності (чим є логарифми), а не мультиплікативності (яким є співвідношення частот). Таким чином, якщо тони x, y, і z утворюють зростаючу послідовність тонів, то міра інтервалу від x до y плюс міра інтервалу від y до z повинні дорівнювати мірі інтервалу від x до z. Така міра задається за допомогою центу, який поділяє октаву на 1200 рівних інтервалів (12 півтонів, що містять 100 центів кожен). Математично, якщо дані тони із частотами f₁ і f₂, кількість центів в інтервалі від f₁ до f₂ становитиме[29]

${\displaystyle \left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.}$

Міліоктава визначається тим самим способом, але матиме множник 1000 замість 1200.[30]

У фотографії, значення експозиції вимірюється як двійковий логарифм від кількості світла, яке досягає плівки або сенсору зображення, у відповідності до закону Вебера-Фехнера, який описує логарифмічний характер сприйняття світла зоровою системою людини. Один крок зміни експозиції є однією одиницею логарифмічної шкали за основою-2.[31][32] Більш точно, значення експозиції фотографії визначається як

${\displaystyle \log _{2}{\frac {N^{2}}{t}}}$

де N це f-число діафрагми, яке вимірює апертуру лінзи під час експозиції, а t це тривалість експозиції в секундах.[33]

Двійкові логарифми також використовуються в денситометрії, щоб оцінити динамічний діапазон світлочутливого матеріалу або цифрового сенсора.[34]

Простим способом розрахувати значення log₂n на калькуляторі, який не має функції log₂, це використати натуральний логарифм (ln), звичайний логарифм (log або log₁₀), які можна знайти в багатьох інженерних калькуляторах. Для цього існує формула зміна основи логарифму:[32][35]

${\displaystyle \log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}},}$

або наближено

${\displaystyle \log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n.}$