Запоминание рекурсивного метода Фибоначчи не быстрее? - PullRequest
Новая
       35

Запоминание рекурсивного метода Фибоначчи не быстрее?

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

Я попытался запоминать рекурсивный метод Фибоначчи, и он возвращает правильное число.Тем не менее, он не появляется быстрее, чем раньше.Я предполагаю, что это потому, что я не использую массив должным образом, чтобы отслеживать, и я все еще делаю избыточные вызовы.Подскажите, пожалуйста, что изменить, чтобы я мог правильно его использовать?

Не уверен, имеет ли это значение, но в глобальной области объявлено fibIndex[] и установлено значение [index + 1] восновной метод после получения ввода.

public static BigInteger fibRec(int index)
{
    BigInteger results; 

    if (index <= 2)
    {
        results = BigInteger.ONE;
    }
    else
    {
        if (fibIndex[index] != null)
        {
            results = fibIndex[index];
        }
        else
        {
            results = fibRec(index - 1).add(fibRec(index - 2));

        }
    }
    return results;
}

Ответы [ 2 ]

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

Я заметил, что вы на самом деле нигде не заполняете fibIndex.Исходя из этого, когда сработает условие if вашего оператора?

Это дает вам представление о том, что нужно исправить?

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

Он не работает быстрее, потому что вы на самом деле не используете памятку, т.е. вы не помещаете результаты в массив.Если вы этого не сделаете, ваша реализация будет на медленнее , потому что вы продолжаете проверять запомненные результаты, которые вы никогда не запомнили.Вот что вам нужно сделать. 

public static BigInteger fibRec(int index) { 
    if (index <= 2) return BigInteger.ONE;

    BigInteger result = fibIndex[index];
    if (result == null) {
        result = fibRec(index - 1).add(fibRec(index - 2));
        fibIndex[index] = result; // you forgot this
    }
    return result;
}

РЕДАКТИРОВАТЬ: Я ранее отметил, что вам не нужно запоминать метод, который вы вызываете только один раз, но потом я вспомнил, что метод рекурсивный.Так что забудьте о том, что я сказал здесь раньше, на самом деле запоминание значительно ускорит метод.

...