Написание функции для F (n) = 0.5F (n-1) - PullRequest
Новая
       11

Написание функции для F (n) = 0.5F (n-1)

0 голосов
/ 03 февраля 2019

пусть F (n) = 0,5F (n-1) и F (0) = 1

a.написать функцию fun1, рекурсивную функцию для оценки n *

b.написать функцию fun2, нерекурсивную функцию для вычисления n-го члена

c.какова временная сложность fun1 и из какого n терма будет лучше использовать fun1 против fun2 в отношении сложности пространства

В общем случае функция оценивает n член последовательности {1,1 / 2, 1 / 4,1 / 8, ...}

a. 

 double fun1( int n ){
    if (n == 0)
        return 1;
    else
        return 0.5*fun1(n-1);
}

b.

double fun2( int n ){
    double sum = 1, i;
    for (i=0 ; i < n; i++)
        sum=sum*(0.5);
    return sum;
}

c.Интуитивно и математически, используя сумму геометрической последовательности, мы можем показать, что это O(n)

  1. Есть ли другой способ?
  2. как решить сложность пространства?

Ответы [ 4 ]

0 голосов
/ 03 февраля 2019

Для рекурсивного и итеративного подхода сложность может быть уменьшена до O (log n) :

Рекурсивная глубина следующего решения составляет log n :

double fun3( int n ){

    double f;
    if ( n == 0 )
        return 1.0;

    f = fun3( n/2 );
    return f * f * (n % 2 ? 0.5 : 1.0);
}

Количество итераций в следующем цикле равно log n : 

double fun4( int n ){

    int i;
    double f = (n % 2 ? 0.5 : 1.0);
    for (i = n; i > 1; i /= 2)
        f *= 0.5*0.5;

    return f;
}
0 голосов
/ 03 февраля 2019

Я понимаю, что это домашний вопрос, поэтому я не буду ссылаться на оптимизацию компилятора и хвостовую рекурсию, поскольку это не является свойством самой программы, но от компилятора зависит, оптимизирует ли он рекурсивную функцию или нет ..

Ваш первый подход явно O (n), так как он вызывает рекурсивно f1 и все, что он делает умножение.

Ваш второй подход также явно O (n), так как это простой цикл.Таким образом, что касается сложности времени, они одинаковы O (n)

Что касается сложности пространства, fun1 требует n записей функций, так что это сложность пространства O (n), в то время как fun2 нужна только одна переменная, поэтому это O (1)космическая сложность.Что касается сложности пространства, fun2 - лучший подход.

0 голосов
/ 03 февраля 2019

Хотя ваши версии fun1 и fun2 имеют разную пространственную сложность, их временная сложность составляет O (n) .

Однаконерекурсивную функцию также можно записать в виде: 

#import <math.h>

double fun2(int n) {
    return pow(0.5, n);
}

Эта функция имеет пространственную и временную сложность O (1) и будет более эффективной для большинства n (вероятно, n > 5).

Что касается исходного вопроса: он очень сложный, поскольку зависит от оптимизации компилятора:

Наивная реализация fun1 имеет сложность пространства O (n) , так как вызов fun1 (n) будет иметь рекурсивную глубину n и, следовательно,требует n фреймов вызова в стеке.На большинстве систем он будет работать только до определенного n .Затем вы получите ошибку Stack Overflow , поскольку размер стека ограничен.

Оптимизирующий компилятор распознает, что это хвостовая рекурсивная функция, и оптимизирует ее до значения, очень близкого к * 1038.* fun2 , который имеет пространственную сложность O (1) , поскольку использует фиксированное число переменных с фиксированным размером, независимым от n и без рекурсии.

0 голосов
/ 03 февраля 2019

Вы можете ответить себе, если посмотрите на сгенерированный код: https://godbolt.org/z/Gd9XxM

  1. Весьма вероятно, что оптимизирующий компилятор удалит хвостовую рекурсию.
  2. Пробели сложность времени сильно зависит от параметров оптимизации (Попробуйте -Os, -O0)
...