當返回命令有兩個遞歸調用時，例如 return fib(n-1) + fib(n-2);，這兩個調用是同時執行的，還是fib(n-1)先執行的fib(n-2)？fib(n-1)通過使用記憶化，時間復雜度降低到 O(n)，但是只有在執行之前fib(n-2)（然后使用存儲的值）才有可能嗎？*public int fib(int n)是一種使用遞歸計算第 N 個斐波那契數的方法。
1 回答
互換的青春
TA貢獻1797條經驗 獲得超6個贊
Java保證表達式中子表達式的求值順序是從左到右。
Java 編程語言保證運算符的操作數以特定的求值順序出現，即從左到右。
這意味著fib(n-1)將在 之前進行評估fib(n-2)。
但是評估順序并沒有改變這里記憶的復雜性，無論哪種方式它仍然是 O(n) 。當 Java 評估它時，fib(n-1)將通過 完成所有備忘錄值n-1，包括 的值fib(n-2)。調用fib(n-2)不做任何工作；它只是引用已經計算出的值fib(n-1)。
如果您顛倒了代碼中的順序：
fib(n-2)?+?fib(n-1)
Thenfib(n-2)將首先被調用，這將通過 完成所有備忘錄值n-2。然后調用fib(n-1)將使用現有的記憶值來“完成工作”，通過 完成所有值fib(n-1)。
無論哪種方式，在評估這些表達式之后，所有通過的值都n-1被記憶，具有 O(n) 的（最壞情況）時間復雜度（和空間復雜度）。也可能這是調用的結果fib(n)，它會額外記住 的值n。
添加回答
舉報
0/150
提交
取消