Какова сложность этой функции c - PullRequest
Новая
       5

Какова сложность этой функции c

4 голосов
/ 25 декабря 2010

в чем сложность следующей функции c? 

double foo (int n) {
    int i;
    double sum;
    if (n==0) return 1.0;
    else {
        sum = 0.0;
        for (i =0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}

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

РЕДАКТИРОВАТЬ:Это был объективный вопрос, заданный на экзамене, и варианты были следующие: 1.O (1) 2.O (n) 3.O (n!) 4.O (n ^ n)

Ответы [ 4 ]

10 голосов
/ 25 декабря 2010

Это Θ (2 ^ n) (предполагая, что f - это время выполнения алгоритма, который у нас есть): 

f(n) = f(n-1) + f(n-2) + ... + 1
f(n-1) = f(n-2) + f(n-3) + ...
==> f(n) = 2*f(n-1), f(0) = 1
==> f(n) is in O(2^n)

На самом деле, если мы игнорируем постоянные операции, точное время выполнения составляет 2 n .

Также в случае, когда вы написали, это экзамен, оба O (n!) и O (n ^ n) верны, и ближайший ответ на Θ (2 ^ n) среди них:O (n!), Но если бы я был студентом, я отмечу их обоих:)

Пояснение к O (n!): 

for all n >= 1: n! = n(n-1)...*2*1 >= 2*2*2*...*2 = 2^(n-1) ==>
2 * n! >= 2^n ==> 2^n is in O(n!),
Also n! <= n^n for all n >= 1 so n! is in O(n^n)

So O(n!) in your question is nearest acceptable bound to Theta(2^n)
2 голосов
/ 25 декабря 2010

С одной стороны, он плохо закодирован:) 

double foo (int n) {         // foo return a double, and takes an integer parameter
    int i;                   // declare an integer variable i, that is used as a counter below
    double sum;              // this is the value that is returned
    if (n==0) return 1.0;    // if someone called foo(0), this function returns 1.0
    else { // if n != 0
        sum = 0.0;           // set sum to 0
        for (i =0; i<n; i++) // recursively call this function n times, then add it to the result
        sum +=foo(i);
        return sum;          // return the result
    }
}

Вы вызываете foo () всего что-то вроде n ^ n (где вы округляете n до ближайшего целого числа)

Например:

foo (3) будет вызываться 3 ^ 3 раза.

Удачи и счастливого Рождества.

РЕДАКТИРОВАТЬ: упс, только что-то исправили.Почему foo возвращает двойной?Он всегда будет возвращать целое число, а не двойное.

Вот лучшая версия с микрооптимизацией!: D 

int foo(int n)
{
    if(n==0) return 1;
    else{
        int sum = 0;
        for(int i = 0; i < n; ++i)
        sum += foo(i);
        return sum;
    }
}
1 голос
/ 25 декабря 2010

Вы могли бы быть немного яснее ... ворчание ворчание 

<n = ?> : <return value> : <number of times called>
n = 0 : 1 : 1
n = 1 : 1 : 2
n = 2 : 2 : 4
n = 3 : 4 : 8
n = 4 : 8 : 16
n = 5 : 16 : 32
n = 6 : 32 : 64
n = 7 : 64 : 128
n = 8 : 128 : 256
n = 9 : 256 : 512
n = 10 : 512 : 1024

number_of_times_called = pow (2, n-1);

Давайте попробуем ввести данные, не так ли?

Используя этот код: 

#include <iostream>

double foo (int n) {
    int i;
    double sum;
    if (n==0) return 1.0;
    else {
        sum = 0.0;
        for (i =0; i<n; i++)
        sum +=foo(i);
        return sum;
    }
}


int main(int argc, char* argv[])
{
    for(int n = 0; 1; n++)
    {
       std::cout << "n = " << n << " : " << foo(n);
       std::cin.ignore();
 }

    return(0);
}

Получим: 

n = 0 : 1
n = 1 : 1
n = 2 : 2
n = 3 : 4
n = 4 : 8
n = 5 : 16
n = 6 : 32
n = 7 : 64
n = 8 : 128
n = 9 : 256
n = 10 : 512

Поэтому, это может быть упрощено до: 

double foo(int n)
{
    return((double)pow(2, n));
}

0 голосов
/ 25 декабря 2010

Функция состоит из нескольких частей.

Первый бит сложности - if(n==0)return 1.0;, поскольку он генерирует только один прогон. Это было бы O(1).

Следующая часть - цикл for(i=0; i<n; i++). Так как это циклы от 0..n это O(n)

Если есть рекурсия, для каждого числа в n вы снова запускаете функцию. И в этой функции снова цикл, и следующая функция. И так далее ...

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

...