Сложность повторного логарифма по основанию 2

Question

Предполагая, что повторный логарифм определен так, как здесь: http://en.wikipedia.org/wiki/Iterated_logarithm

Как я должен идти о сравнении его сложности с другими функциями, например lg(lg(n))? До сих пор я делал все сравнения, вычисляя пределы, но как рассчитать предел повторного логарифма?

Я понимаю, что растет очень медленно, медленнее, чем lg(n), но есть ли какая-то функция, которая растет с той же скоростью, может быть, как lg*(n) (где lg* итеративный логарифм по основанию 2), поэтому было бы легче сравнить его с другими функциями? Таким образом, я мог бы также сравнить lg*(lg(n)) в lg(lg*(n)) например. Буду признателен за любые советы по сравнению функций друг с другом на основе скорости роста.

Answer 1

Функцию повторного логарифма log* n нелегко сравнить с другой функцией, которая имеет аналогичное поведение, так же, как log n нелегко сравнить с другой функцией с аналогичным поведением.

Чтобы понять функцию log *, я счел полезным помнить несколько вещей:

1. Эта функция растет очень медленно. Представьте, что log * 2²²²² = 5, и эта башня из 2 - это величина, превышающая количество атомов в известной вселенной.
2. Он играет с логарифмами так же, как логарифмы с делением. Правило частного для логарифмов гласит, что log (n / 2) = log n - log 2 = log n - 1, при условии, что наши журналы имеют основание-2. Одна интуиция для этого заключается в том, что в некотором смысле log n представляет "сколько раз вам нужно разделить n на два, чтобы уменьшить n до 1?", Поэтому log (n / 2) "должно" быть log n - 1. потому что заранее сделали одно дополнительное деление. С другой стороны, (log n) / 2, вероятно, намного меньше, чем log n - 1. Точно так же log* n подсчитывает, "сколько раз вам нужно взять журнал n, прежде чем вы опустите n до некоторой константы? " поэтому log * log n = log* n - 1, потому что мы взяли еще один журнал. С другой стороны, log log* n, вероятно, намного меньше log* n - 1.

Надеюсь это поможет!