Попытка вычислить время и сложность хранения для функции (C)

Question

edit: я понял, как правильно рассчитать сложность времени, но все еще не могу понять сложность хранилища.

edit: все понял.

Я пытался решить вопрос сложностии не удалось.

Ответ должен быть таким: сложность времени - n (m + n), сложность хранения - m + n.

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

Вот функция:

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

Из того, что я вижу, "free (arr)" освобождает память, выделяемую malloc, что делает malloc irelaventс точки зрения сложности времени.редактирование: кто-то объяснил мне, что, хотя мы используем 'free', malloc по-прежнему принимается во внимание (мудрый пробел).

Я вижу, что первый вызов функции заставляет сам вызов функции n раз, и когда это происходитm увеличивается в 1 - n раз, поэтому временная сложность для первого вызова func равна n (m + 1), а сложность хранения n-, поскольку в рекурсии имеется n вызовов функции.edit: выяснил это в конце концов.

Второй вызов функции вызывает функцию log (n) раз, а m увеличивается log (n) раз, что усложняет время для этого вызова: log (n) (m +)1).Сложность хранения: log (n).

Таким образом, общая сложность времени равна n (m + 1), общая сложность хранения равна n.

Answer 1

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

Давайте проведем рефакторинг:

void f1(int m) {
    int *arr = malloc(m*sizeof(int));
    for (int i = 0; i < m; i++) {
        arr[i] = 0;
    }
    free(arr);
}

void f(int n, int m){
     if (n <= 1) {
         f1(m);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

Так что для f1 это довольно просто, - сложность пространства равна sizeof(int) * m - нам нужно выделить это много - а сложность времени всего лишь m -мы перебираем все m элементы в массиве arr.

. n%2 может быть только 1 или 0, поэтому мы можем заменить f(n%2, m+1); на f1(m+1).

void f(int n, int m){

     if (n <= 1) {
         f1(m); // (1)
         return;
     }

     f(n-1, m+1); // (2)

     f1(m + 1); // (3)
}

Сейчас.Если n > 1, то мы звоним f(n-1, ... до n <= 1.Для каждого n > 1 мы вызываем f1(m + 1) в обратном хронологическом порядке (потому что это после рекурсивного вызова).Когда мы добираемся до n <= 1, тогда f1(m) вызывается с m = m(initial) + n(initial) - 1 разами.Ох, может быть, например, пример для n=5, тогда:

• начальный вызов f(5, m), поэтому n = 5
• n = 5, поэтому мы вызываем f(4, m+1) // (2)
• n = 4, поэтому мы называем f(3, m+2) // (2)
• n = 3, поэтому мы вызываем f(2, m+3) // (2)
• n = 2, поэтому мы вызываем f(1, m+4) // (2)
• n = 1, поэтому мы вызываем f1(m+4) и возвращаем // (1)
• n = 2,после (2), поэтому мы вызываем f1(m+4) // (3)
• n = 3, после (2), поэтому мы вызываем f1(m+3) // (3)
• n =4, после (2), поэтому мы вызываем f1(m+2) // (3)
• n = 5, после (2), поэтому мы называем f1(m+1) // (3)

Мы можем видеть, что f1(m+4) вызывается дважды, и что мы вызываем f1(m + i) в обратном порядке от i=1 до i=4.

Мы можем "раскрыть" функцию:

void f(int n, int m){
     f1(m + n - 1);
     for (int i = n - 1; i > 0; --i) {
         f1(m + i);
     }
}

Когда m и n приближаются к бесконечности, +1 или -1 ничего не значат.

Пространственная сложность - это сложность пространства f1(max(m + i, m + n - 1)), потому что f1 освобождает память каждый раз.Так что (m + n - 1) * sizeof(int), что составляет (m + n) * sizeof(int), то есть m + n.

Сложность времени зависит от того, сколько раз мы вызываем функцию f1.Мы видим, что мы называем:

f1(m + n - 1)
f1(m + n - 1)
f1(m + n - 2)
...
f1(m + 2)
f1(m + 1)

Таким образом, сложность времени составляет

(m + n - 1) + ((m + n - 1) + (m + n - 2) + ... + (m + 1))
(m + n - 1) + (n - 1) * m + ((n - 1) + (n - 2) + ... 1)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
// the `*2`, `/2`, `+1` and `-1` mean nothing close to infinity
 m + n      + n       * m + n        *  n
m + n + m * n + n * n
m * (n + 1) + n * (n + 1)
(m + n) * (n + 1)
(m + n) * n

Answer 2

Это на самом деле сложный вопрос!Второй вызов функции f(n%2, m+1) просто вызывает рекурсивный f один раз, потому что он вычисляет напоминание от n до 2, которое может быть 1 или 0!и в обоих случаях функция f возвращается без какого-либо дополнительного рекурсивного вызова.Так что это не log n.

Функция f вызывается один раз в f(n-1, m+1) n раз, и сразу после этого в f(n%2, m+1) она будет вызываться снова еще раз.Тогда это O (2n), если учитывать только n-фактор.

Теперь, учитывая m-фактор, мы заметим, что цикл внутри if повторяется m раз, и m увеличивается на единицу при каждом рекурсивном вызове (ифактически уменьшается, когда он возвращается обратно из рекурсивного вызова!), поэтому это будет сумма (m + n ... m + 1), которая равна O (mn + n (n + 1) / 2).Это после упрощения.

Поэтому, учитывая оба фактора, сложность времени равна O (2n + mn + n (n + 1) / 2), что фактически после упрощения эквивалентно O (nm + n ^ 2) .

Относительно сложности хранения: m увеличивается для первого вызова (m + 1), который будет продолжаться в течение n раз, но второй вызов не продолжается,поэтому сложность хранения будет O (n + m) .