Как найти T (n) этой функции?

Question

Функция:

for (int i = 0; i < n; i++) {
    for (int j = i; j > 0; j /= 2){
        std::cout << j << endl;
    }
}

Я только что познакомился с этим материалом, и эта проблема сбивает меня с толку. Поскольку внутренний цикл for связан с i, похоже, он будет запускать log (n!) Раз. То есть, поскольку log (a) + log (b) = log (a * b). И внешний цикл запускается n раз. Хотя я все еще облажаю свой ответ и не уверен, как именно все соединить / как еще я мог бы пойти по этому поводу. Любая помощь?

Answer 1

Конечно, ваш подход кажется нормальным.

Существует альтернативный взгляд на вопрос.

for (int i = 0; i < n; i++) { // loop 1
    for (int j = i; j > 0; j /= 2){ // loop 2
        std::cout << j << endl;
    }
}

Анализ цикла 1

Здесь нечего видеть, просто O(n)

Анализ цикла 2

Немного более интересно, учитывая число j (= i), это гонка, чтобы увидеть, сколько раз вы можете разделить на 2, прежде чем доберетесь до 0. Что, конечно, не что иное, как логарифмическая база 2 числа.

Комбинируя оба анализа для каждого n, вы выполняете журнал (n, 2) -> log (число, база).

То есть O(n * log(n,2)).

чем-то, что называется Приближение Стирлинга , вы можете доказать, что O(nlogn) есть O(log(n!)).

Теперь необходимо указать, что вы попросили T(n), что немного отличается O(n).

T(n) - это то, что вы используете для математического обозначения алгоритма относительно его следующих шагов обработки и текущего шага.

Для чего-то вроде сортировки слиянием

T(n) = 2 * T(n/2)(divide) + O(n)(conquer).

В нашем случае я бы написал T(n) как

T(n) = T(n + 1)(next step) + O(logn)(race to zero)   , 0 <= n < N
     = 0                                             , n >= N

(я знаю, что T (n) обычно обозначается в терминах предыдущих терминов, а не будущих терминов, но я просто обрисовываю точку, это не строгое математическое определение)

Answer 2

Чтобы рассчитать время запуска внутреннего цикла, выполните следующее: цикл останавливается, когда j = 0 и j start = i, и каждый раз, когда половина iself, поэтому на итерации k вы получаете i / 2 ^ k, когда i / 2 ^ k = 1, он достигает последней итерации, поэтому мы берем log2 и результат равен k = log2 (i) +1, плюс один, потому что требуется еще одна итерация. Таким образом, внутренний цикл принимает k = log2 (i) +1 итерация. Теперь вы можете выразить количество времени выполнения двух циклов как: Сумма для i = 1 до i = N суммы для j = 1 до j = \ log2 (i) +1 \ of 1.

Однако, если вас интересует T (n), просто умножьте количество раз внешнего цикла на максимальное время внутреннего цикла, поэтому максимум внутреннего цикла равен log2 (n), и вы получите: T (n) = O (n log2 (n))

Где \ log2 (i) +1 \ - нижнее целое число