Вычисление наибольшего значения int меньше, чем база 2 log N - PullRequest
Новая
       14

Вычисление наибольшего значения int меньше, чем база 2 log N

0 голосов
/ 29 декабря 2018

Я читал Алгоритмы, 4-е издание, и он определяет вопрос следующим образом:

Напишите статический метод lg(), который принимает int значение N в качестве аргумента ивозвращает наибольший int, не превышающий логарифм base-2 N в Java.Не используйте Math.

Я обнаружил следующее решение: 

public static int lg(int N) {
    int x = 0;
    for (int n = N; n > 1; n/= 2) x++;
    return x;
}

Мне интересно, почему это решение работает.Почему деление на 2 непрерывно позволяет нам найти наибольшее целое число, меньшее, чем логарифм аргумента для основания 2?Я понимаю Java, но не так, как работает этот конкретный алгоритм.

Спасибо.

Ответы [ 4 ]

0 голосов
/ 29 декабря 2018

Мы ищем наибольшее целое число x, такое что x <= log_2 (N), то есть 2 ^ x <= N </p>

или эквивалентное 2 ^ x <= N <2 ^ {x + 1} </p>

Пусть N_0 = N

, а для k> 0 N_k является частным от деления N_ {k-1} на 2 и r_k в {0, 1} остатка (N_ {k-1} = 2.N_k + r_k)

Имеется:

2 ^ {x-1} <= N_1 + (r_1 / 2) <2 ^ x </p>

Но 0 <= r_1 / 2 <= 1/2, а остальные числа являются целыми числами, что эквивалентно </p>

2 ^ {x-1} <= N_1 <2 ^ x </p>

Мы имеем последовательно:

2 ^ {x-1} <= N_1 <2 ^ x </p>

2 ^ {x-2} <= N_2 <2 ^ {x-1} </p>

…

2 ^ {xx} <= N_x <2 ^ {x-x + 1} </p>

Последнее также записано 1 <= N_x <2 </p>

Но N_x является целым числом, поэтому N_x = 1

Следовательно, x - это число деления на 2 из N, которое остается большим или равным 1.

Вместо того, чтобы начинать с N_1, мы можем начатьиз N_0 = N и оставайтесь больше 1.

0 голосов
/ 29 декабря 2018

Тривиально следует из логарифмического тождества log(a/b) = log(a) - log(b).

Вы ищете наибольшее целое число x, чтобы: 

x <= log2(n)

Используя приведенное выше тождество и принимая во вниманиечто log2(2) = 1 мы получаем: 

x <= log2(n/2) + log2(2)
x <= log2(n/2) + 1
x <= log2(n/4) + 2
x <= log2(n/8) + 3
...
x <= log2(1) + k            
x <= k                   (since log2(1) = 0)

Так x - это количество раз, которое вы поделили n на 2 до достижения 1.

0 голосов
/ 29 декабря 2018

Ответ чисто математический,

log₂ (n) = ln (n) / ln (2) = x

Применяя правила экспоненциальной:

ln (n) = ln (2) * (x)

n = 2 ^ x

Поэтому вы должны делить на 2 дозначение меньше 1, чтобы получить ближайший к нему int.

0 голосов
/ 29 декабря 2018

Это связано со свойствами показателей и логарифмов.Главное наблюдение, которое вам нужно, это то, что

2 lg n = n,

, потому что логарифмы являются обратными экспонентами.Перестановка этого выражения дает

1 = n / 2 lg n .

Другими словами, значение lg n - это количество развам нужно разделить n на два, чтобы уменьшить его до 1. Это, кстати, очень хорошая интуиция, которую нужно иметь при изучении алгоритмов, так как термины лога все время появляются в контекстах, подобных этим.

Здесь есть некоторые другие нюансы о том, как работает целочисленное деление, но это основная идея, почему этот код работает.

...