найти временную и пространственную сложность

Мне нужно найти временную и пространственную сложность f3. Я думаю, что g имеет пространственную сложность log(n), поэтому для временной сложности, но я не совсем уверен, как мне найти временную и пространственную сложность f3, потому что вызов g находится внутри команды for, означает ли это, что g вызывается каждый раз, чтобы проверить, если g(i) < n?

int g(int n)
{
    if (n <= 1) 
        return 1;
    return g(n / 2) + 1;
}

int f3(int n)
{
    int counter = 0;
    for (int i = 0; g(i) < n; ++i)
        ++counter;
    return counter;
}

c time-complexity space-complexity
person tomer    schedule 15.08.2020    source источник
comment
Сколько раз f3 вызывает g?   -  person Tarik    schedule 15.08.2020

Ответы (2)


arrow_upward
0
arrow_downward

Вкратце:
Временная сложность f3(n) = O(2^n)

Пространственная сложность f3(n) = O(n)

Пространственная и временная сложность g(n) = O(log(n))

Примечание: (здесь все журналы, на которые я ссылаюсь, являются log base2 link и все обозначения в нотации Big O)

Подробности:

Функция g() возвращает пол(log(n))+1. Цикл в функции f3() продолжается до тех пор, пока функция 'g()' не вернет n. Чтобы g(i) возвращал 'n', i должно быть '2^(n-1)'.

Чтобы завершить цикл в f3(), 'i' должно достичь 2^(n-1). Итак, 'g()' вызывается 2^(n-1) раз.

Итак, Временная сложность f3() = 2^(n-1) x (временная сложность g()) = 2^n x (log n) = O(2^n)< /сильный>

Самая большая используемая память будет во время последнего вызова 'g(i)', где i==2^(n-1).

Поэтому пространственная сложность f3() = log(2^(n-1)) = O(n)

person Darshan K N    schedule 15.08.2020
comment
Вывод «Так что временная сложность f3() = 2^n x (временная сложность g())» недействителен: хотя f3 может выполнять итерацию 2^n раз, она вызывает g с переменным аргументом, поэтому сложность f3 равна сумма сложностей различных вызовов g, а не продукт одной сложности. Сложность Big O может сработать так же, но в ответе это не показано. - person Eric Postpischil; 15.08.2020
comment
Спасибо за указание на пол (log (n)) + 1, я пропустил рассмотрение g (степени 2), иначе он удовлетворяет ceil (log (n)). - person Darshan K N; 16.08.2020
comment
Это упоминается в ответе как Обратите внимание, что все расчеты сложности предназначены для Big O, а все журналы имеют основание 2. - person Darshan K N; 16.08.2020
comment
Если ваш второй комментарий, относящийся к примечанию, является ответом на мое утверждение о том, что вывод о временной сложности неверен, то он не имеет значения. Эта проблема не связана с нотацией Big O или основанием логарифма. Проблема в том, что сложность for (i = 0; i < N; ++i) q(i), вообще говоря, не является сложностью, в N раз превышающей сложность q(i). Например, если q(i) делает ровно 2^i шагов, O(q(i)) = 2^i. Но сложность цикла не N•q(N-1). Вызовы q в цикле займут 1+2+4+8+…2^i = 2^N−1 шагов. Сложность этого цикла O(2^N). - person Eric Postpischil; 16.08.2020
comment
В примечании я хотел сказать, что все расчеты действительны только при расчете для Big O. Я согласен с тем, что точную временную сложность нельзя взять вообще за N раз. Но с учетом большого O это просто приведет к O (2 ^ n). - person Darshan K N; 16.08.2020

arrow_upward
0
arrow_downward

Поскольку g(n) будет выполняться в Theta(log(n)) и каждый раз добавлять 1 к конечному результату, окончательное значение g(i) будет \ceil{log(i)} + 1. С другой стороны, цикл внутри f3 будет выполняться, пока g(i) < n. Это означает, что цикл будет повторяться до 2^n. Следовательно, f3 будет выполняться 2^n раз. Следовательно, временная сложность f3(n) = sum_{i=1}^{2^n} log(i) = log((2^n)!) = \Theta(n * 2^n) (как log((2^n)!) ~ (2^n) log(2^n)).

Что касается пространственной сложности, максимальная глубина g(i) будет при i = 2^n, то есть n (n рекурсивных вызовов). Следовательно, пространственная сложность f3 будет \Theta(n).

person OmG    schedule 15.08.2020