Что такое цифры в базе 2 ^ lg n?

Question

Я работал над множеством алгоритмов сортировки, и есть один, называемый сортировкой по основанию, в котором я должен сортировать числа по основанию 2 ^ (lg n), но я точно не знаю, что это такое. Я имею в виду, что я знаю, что база 2 двоичная, но с log n я просто не понимаю.

Итак, мне было интересно, что такое base 2 ^ (lg n) на самом деле и каким образом это повлияет на мой код.

Answer 1

В вопросе отсутствует информация: какова основа lg (): и является ли n максимальным диапазоном значений или если n - количеством элементов. Также в инструкции должна быть функция потолка (округление дроби до следующего целого числа).

Предполагая, что n - это максимальный диапазон значений, где n = max () + 1 - min ():

Если lg = log2, то это 2 ^ (ceil (log2 (n ))), который равен n или следующей степени 2> n, если n не является степенью 2. При сортировке чисел можно также использовать сортировку счетом вместо сортировки по основанию.

Если lg = log4, тогда это 2 ^ (ceil (log4 (n))). Например, если n = 1024, то 2 ^ (ceil (log4 (1024))) == 2 ^ 5 == 32, и для сортировки данных потребуется 2 прохода сортировки по основанию (обычно наименее значимый di git) .

Если lg = log16, то это 2 ^ (ceil (log16 (n))). Например, если n = 65536, то 2 ^ (ceil (log16 (65536))) == 2 ^ 4 == 16 и потребуется 4 прохода сортировки по основанию для сортировки данных.

В качестве примечания , на типичном P C (процессор X86), если используется сортировка по основанию для 32-битных или 64-битных целых чисел без знака, использование 2 ^ 8 == 256 обычно является самым быстрым, даже если это означает больше проходов, чем использование чего-то вроде 2 ^ 16 == 65536.

Answer 2

Обозначение lg n является сокращением для log ₂ n.

Учитывая это, можете ли вы упростить 2 ^{lg n} = 2 ^{log ₂ п} ?