Rust代码对比｜Rust编程一对一答疑｜留学生编程辅导

1. Question

你好，我是悦创。

学生提问：两段代码后者的优势是什么

代码如下：

use std::collections::HashMap; 
pub fn f(x:u64)-> u64 {
    match x{
        0 => panic!("fibonacci not defined for argument 0!"),
        1|2 => 1,
        _   => f(x-1)+f(x-2)
    }
}

pub fn fibonacci_i(n: u64) -> u64 {
// we cache the results in a hash map O(1) access time
    let mut fib_cache: HashMap<u64, u64> = HashMap::new();
    fn fi(n: u64, fib_cache: &mut HashMap<u64, u64>) -> u64{
        match n {
            0 => panic!("fibonacci not defined for argument 0!"),
            1 | 2 => 1,
            _ => match fib_cache.get(&n) {
                Some(r) => *r,
                None => { let r=fi(n-1, fib_cache)+fi(n-2, fib_cache);
                    fib_cache.insert(n,r); r }
            },
        }
    }
    fi(n, &mut fib_cache)
}

解答

这两段 Rust 代码都实现了 Fibonacci 数列的计算，但它们在实现方式上有显著差异，导致了第二段代码（fibonacci_i 函数）相较于第一段代码（f 函数）有以下几个优势：

1. 使用缓存（Memoization）：第二段代码使用了一个 HashMap 来缓存已经计算过的 Fibonacci 数值。这种方法称为 memoization，能显著减少重复计算，特别是在计算较大的 Fibonacci 数值时。例如，f(50) 调用会进行大量重复的计算，而在 fibonacci_i(50) 中，每个中间结果只计算一次并存储起来供后续使用。

2. 时间复杂度改进：第一段代码的时间复杂度为 $O(2^n)$，因为它采用了递归但没有任何优化措施，所以随着 x 的增加，计算量呈指数级增长。相反，第二段代码通过缓存先前的计算结果，将时间复杂度降低到大约 $O(n)$。

3. 空间复杂度：尽管第二段代码使用了额外的空间来存储中间结果（HashMap），这增加了空间复杂度，但这种空间的使用是有意义的，因为它极大地提升了程序的执行效率，特别是在计算大数值时。这种空间换时间的策略是算法优化中常见的方法。

总之，第二段代码的主要优势在于通过使用 memoization 来避免重复计算，从而大幅提高了算法的效率，这在处理大规模数据时尤为重要。这样的设计使得函数能够更加高效地处理大数值输入，适用于需要频繁计算或需要计算大数值 Fibonacci 数的场景。