具有回溯的Fibonacci序列仍比正常的递归解慢
我注意到我的递归Fibonacci算法只适用于大于12的值。
我将它与另一个方法的实现进行了比较，在该方法中，他还传递了一个数组。我认为每次传递一个数组，在重新调用该方法时会占用太多的内存，从而使程序变得更慢，但事实并非如此。
我仍然无法理解我的外部数组如何没有比普通的递归Fibonacci算法更快。我想可能是因为我的if中有很多条件，我检查它是否慢，但我不确定。
如果可能的话，你会看我的代码并告诉我我做错了什么或者后台发生了什么吗？
public class Fibonacci2 {
int memory[];
public Fibonacci2(int f) {
if (memory == null) {
memory = new int[f+1];
memory[0] = 0;
memory[1] = 1;
memory[2] = 1;
}
}
public int recursive(int f) {
if (memory[f-1] != 0 && memory[f-2] != 0 && f>2) {
memory[f] = memory[f-1] + memory[f-2];
} else if (memory[f-1] == 0 && memory[f-2] != 0 && f>2) {
memory[f] = recursive(f-1) + memory[f-2];
} else if (f>2) {
memory[f] = recursive(f-1) + recursive(f-2);
}
return memory[f];
}
}
public class Fibonacci1 {
public Fibonacci1() {}
public int recursive(int f) {
if (f > 2) {
return recursive(f-1) + recursive(f-2);
} else {
return 1;
}
}
}
public class Main {
public static void main(String[] args) {
int fibo = 12;
Fibonacci1 fiboEx1 = new Fibonacci1();
Fibonacci2 fiboEx2 = new Fibonacci2(fibo);
int a = fiboEx1.recursive(fibo);
long start = System.nanoTime();
long stop = System.nanoTime();
System.out.println("fibo of " + fibo + " is " + a);
System.out.println("Fibonacci time without memorization: " + (stop-start));
int b = fiboEx2.recursive(fibo);
start = System.nanoTime();
stop = System.nanoTime();
System.out.println("fibo of " + fibo + " is " + b);
System.out.println("Fibonacci time with memorization: " + (stop-start));
}
}回答 1
Stack Overflow用户
发布于 2020-11-16 12:13:11
我注意到，我的递归Fibonacci算法只对大于12的值起作用。
我猜你的意思是写“小于12的值”。无论哪种方式，这都不是真的:您的解决方案对值>12起作用，直到结果类型溢出。
也就是说，您的代码存在多个问题。
- 不要在构造函数中测试
if(memory==null)。永远都是真的。--
memory[f-1] != 0 && memory[f-2] != 0 && f>2-你为什么在这里测试f > 2？只有在一开始对其进行测试时，测试才有意义，以避免访问负数组元素。否则，测试是多余的。
- 整个函数比需要的要复杂得多。分离访问回忆录值的逻辑，使其更清晰、更简单、更不容易出错：
公共int递归(Int f){ if (f >2& memoryf 2 == 0) { memoryf 2=递归(f - 2)；} if (f>1& memoryf 1 == 0) { memoryf 1=递归(f- 1)；} memoryf = memoryf 2+ memoryf 1；
*…当然，您可以并且应该进一步简化这一点：
公共int递归(Int f){ if (memoryf == 0) { memoryf =递归(f-2)+递归(f-1)；}返回内存；}
这也是一样的。但是，不是每个函数调用对回忆录的值执行多个冗余检查，它只是处理自己的值(即f)，并为其余的值调用自己。
- Fundamentally，将其作为类具有构造函数和附加函数是没有任何意义的:该函数只能用于获取单个值的Fibonacci数，此外，该值在构造函数和函数调用中需要相同(这很容易出错！)。例如，以下代码崩溃：
new Fibonacci2(10).recursive(15)。new Fibonacci2(1)也是如此。好的代码不会允许这样的错误发生。
这里有一个没有这些问题的解决方案：
class Fib {
static int memory[];
private static void resizeMemory(int newSize, int[] oldValues) {
if (newSize < 3) newSize = 3;
memory = new int[newSize];
System.arraycopy(oldValues, 0, memory, 0, oldValues.length);
}
public static int fib(int n) {
if (memory == null || memory.length <= n) {
resizeMemory(n + 1, new int[] {0, 1, 1});
}
if (n == 0) return 0;
if (memory[n] == 0) memory[n] = fib(n - 2) + fib(n - 1);
return memory[n];
}
}但我仍然不会像这样编写“真正的”fibonacci实现--维护全局内存缓存会带来复杂性，而且没有真正的用途。这里有一个不使用缓存的高效实现。实际上，如果计算大量fibonacci数，效率就会降低，即使这样，这也不太可能成为瓶颈。
为了说明这一点，如下所示：
private static int fibImpl(int n, int a, int b) {
if (n == 0) return a;
if (n == 1) return b;
return fibImpl(n - 1, b, a + b);
}
public static int fib(int n) {
return fibImpl(n, 0, 1);
}https://stackoverflow.com/questions/64857578
复制相似问题
腾讯云开发者
