большой порядок рекурсивных и итерационных функций Фиби? - PullRequest
Новая
       4

большой порядок рекурсивных и итерационных функций Фиби?

4 голосов
/ 11 мая 2011

Меня попросили написать функцию fib наиболее эффективным способом?

Это реализация, которую я предоставил: 

public static int fib(int n)
{
    int prev1 = 1, prev2 = 1, ans = 1, i = 3;

    while (i <= n)
    {
        ans = prev1 + prev2;
        prev1 = prev2;
        prev2 = ans;
        i++;
    }
    return ans;
}

Это наиболее эффективно?Что такое большой заказ?

Меня также попросили дать большое обозначение рекурсивной реализации: 

public static int recursiveFib(int n)
{
    if (n <= 2)
        return 1;
    else
        return recursiveFib(n-1) + recursiveFib(n - 2);
}

Я думаю, что это экспоненциальное 2 ^ n, поэтому оно неэффективно.

Ответы [ 3 ]

8 голосов
/ 11 мая 2011

Ваша реализация - O(n), и это нормальный способ реализации функции Фибоначчи.Рекурсивное определение - O(fib(n)), если не используется памятка или подобное.

Существует также выражение закрытой формы чисел Фибоначчи и Эта ссылка имеет некоторые реализацииболее быстрых функций fib.

3 голосов
/ 11 мая 2011

Я бы сказал, что лучший способ найти fib для определенного n - это использовать метод вычисления матрицы, как указано в Link - Page19

enter image description here

, где F0 = 0 и F1 = 1. Это матричное соотношение легко использовать для нахождения fib для любого значения n и n + 1. Самое приятное то, что матрицу умножения не нужно умножать n раз, а только logN раз, чтобы найти фактическое значение множителя. Таким образом, общая полнота алгоритма составляет всего O (logN).

Уравнение получено из основного соотношения

F1 = 0 * F0 + 1 * F1

F1 = 1 * F0 + 1 * F2

Итерируя по n, матрицу умножения нужно умножить n раз.

2 голосов
/ 13 мая 2011

Вот метод матрицы для заполнения этой страницы: 

public static void main(String[] args)
{
    int n = 25;
    matMul(n - 1);
    System.out.printf("\n%dth Fibonnacci number : %d\n\n", n, M[0][0]);
}

static int[][] M = {{1,0},{0,1}};
static int[][] A = {{1,1},{1,0}};
static int[][] C = {{0,0},{0,0}};

static void matMul(int n)
{
    if (n > 1)
    {
        matMul(n/2);
        mulM(0);
    }
    if (n%2!=0)
    {
        mulM(1);
    }
}

static void mulM(int m)
{
    int i,j,k;

    if (m==0)
    {
        for (i=0;i<2;i++)
            for (j=0;j<2;j++)
            {
                C[i][j]=0;
                for (k=0;k<2;k++)
                    C[i][j]+=M[i][k]*M[k][j];
            }
    }
    else
    {
        for (i=0;i<2;i++)
            for (j=0;j<2;j++)
            {
                C[i][j]=0;
                for (k=0;k<2;k++)
                    C[i][j]+=A[i][k]*M[k][j];
            }
    }
    for (i=0;i<2;i++)
            for (j=0;j<2;j++)
            {
                M[i][j]=C[i][j];
            }
}
...