下面把 从最慢到最快（O(log N)） 的 Fibonacci 在 Python 中常见实现方式一次性给你总结，包含完整代码 + 要点说明。全部都能面试直接写。
✅ 1. 最基础：递归（指数级 O(2^N)）——最慢，仅展示
def fib_rec(n): if n < 2: return n return fib_rec(n-1) + fib_rec(n-2)
✅ 2. 带缓存的递归（O(N)）
2.1 functools.lru_cache
from functools import lru_cache @lru_cache(None) def fib_cache(n): if n < 2: return n return fib_cache(n-1) + fib_cache(n-2)
✅ 3. 迭代写法（O(N)，最快的线性级别）
def fib_iter(n): if n < 2: return n a, b = 0, 1 for _ in range(n-1): a, b = b, a + b return b
⭐⭐⭐ 4. 矩阵快速幂（O(log N)）——面试最常用
Fibonacci 可由矩阵快速幂得到：
实现：
def mat_mul(A, B): return [ [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]], [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]] ] def mat_pow(M, n): # fast exponentiation result = [[1,0],[0,1]] # identity matrix while n > 0: if n & 1: result = mat_mul(result, M) M = mat_mul(M, M) n >>= 1 return result def fib_matrix(n): if n == 0: return 0 M = [[1,1],[1,0]] R = mat_pow(M, n-1) return R[0][0] # = F_n
时间复杂度 O(log N)
空间复杂度 O(1)
⭐⭐⭐ 5. 快速倍增法（Fast Doubling Method，O(log N)）——最快，也最优雅
利用性质：
实现：
def fib_fast_doubling(n): def helper(n): if n == 0: return (0, 1) # (F_n, F_{n+1}) a, b = helper(n // 2) c = a * (2*b - a) d = a*a + b*b if n % 2 == 0: return (c, d) else: return (d, c + d) return helper(n)[0]
优势：
- 纯递归，但深度只有 O(log N)
- 常数更小，实际运行比矩阵幂更快
- 面试官最喜欢的 O(log N) 写法
⭐⭐⭐ 6. Binet Formula（闭式公式）——O(1) 但不精确（浮点误差）
理论上：
其中 ()
但 Python 浮点会在 n≈70 后崩溃，基本不用。
import math def fib_binet(n): phi = (1 + 5**0.5) / 2 return int(round(phi**n / math.sqrt(5)))
📌 总结（从慢→快）
方法 | 时间复杂度 | 准确性 | 面试推荐度 |
递归 | O(2^N) | ✔ | ❌ |
记忆化递归 | O(N) | ✔ | ✔ |
迭代求解 | O(N) | ✔ | ✔（基础） |
矩阵快速幂 | O(log N) | ✔ | ⭐⭐⭐ |
Fast Doubling | O(log N) | ✔ | ⭐⭐⭐⭐⭐ |
Binet（闭式） | O(1) | ❌（浮点） | ❌ |
🚀 如果你面试，只推荐这段（Fast Doubling）
def fib(n): def helper(n): if n == 0: return (0, 1) a, b = helper(n // 2) c = a * (2*b - a) d = a*a + b*b return (c, d) if n % 2 == 0 else (d, c + d) return helper(n)[0]
这是 最快、最简洁、最常用的 O(log N) Fibonacci。
如果你希望我加：
- benchmark 对比（timeit）
- 所有方法的运行速度图
- 解释矩阵幂公式推导
- C++ 版本
我也可以继续补。
def my_sqrt(x: float, tol: float = 1e-8) -> float: if x < 0: raise ValueError("x must be >= 0") if x == 0: return 0.0 # 初始猜测：可以用 x 或 x/2，或者更聪明点用 1 guess = x while True: new_guess = 0.5 * (guess + x / guess) # Newton 法核心公式 if abs(new_guess - guess) < tol: return new_guess guess = new_guess print(my_sqrt(9)) print(my_sqrt(10)) print(my_sqrt(0.25))
def max_profit_1(prices): # 实际是找最小利润（最负） max_price_so_far = prices[0] min_profit = float("inf") for p in prices[1:]: # 卖出价格 p，买入价格 max_price_so_far（最亏） min_profit = min(min_profit, p - max_price_so_far) # 更新历史最高买点（为了以后更亏） max_price_so_far = max(max_price_so_far, p) return min_profit
def max_profit_2(prices): buy1 = -float("inf") sell1 = float("inf") buy2 = -float("inf") sell2 = float("inf") for p in prices: buy1 = max(buy1, p) # 尽可能贵买入（为了最亏） sell1 = min(sell1, p - buy1) # 一次交易的最小利润（最负） buy2 = max(buy2, p - sell1) # 第二次买时抵扣第一次亏损 sell2 = min(sell2, p - buy2) # 两次交易的最小总利润 return sell2
import random def estimate_pi(n_samples: int = 1_000_000) -> float: inside = 0 for _ in range(n_samples): x = random.random() # [0, 1) y = random.random() # [0, 1) if x*x + y*y <= 1.0: # 落在 1/4 圆内 inside += 1 return 4.0 * inside / n_samples if __name__ == "__main__": print(estimate_pi(100_000))
class PriceTracker: def __init__(self): self.prices = {} # product_code -> price def add_price(self, product_code: str, price: float): """Record or update the price for a product.""" self.prices[product_code] = price def get_max_price_for_products(self, product_sub_code: str) -> float: """Return the max price for products whose code starts with product_sub_code.""" max_price = -1 prefix = product_sub_code for code, price in self.prices.items(): if code.startswith(prefix): if price > max_price: max_price = price return max_price if __name__ == "__main__": p = PriceTracker() p.add_price("abcdef", 5) p.add_price("abcfde", 6) p.add_price("abcd", 2) assert p.get_max_price_for_products("a") == 6 assert p.get_max_price_for_products("ab") == 6 assert p.get_max_price_for_products("abcd") == 5 assert p.get_max_price_for_products("ad") == -1 print("All tests passed.")
class TrieNode: def __init__(self): self.children = {} self.max_price = -1 # 经过此节点的所有产品的最高价 class PriceTracker: def __init__(self): self.root = TrieNode() def add_price(self, product_code: str, price: float): node = self.root for ch in product_code: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.max_price = max(node.max_price, price) # update prefix-max def get_max_price_for_products(self, product_sub_code: str) -> float: node = self.root for ch in product_sub_code: if ch not in node.children: return -1 node = node.children[ch] return node.max_price if __name__ == "__main__": p = PriceTracker() p.add_price("abcdef", 5) p.add_price("abcfde", 6) p.add_price("abcd", 2) assert p.get_max_price_for_products("a") == 6 assert p.get_max_price_for_products("ab") == 6 assert p.get_max_price_for_products("abcd") == 5 assert p.get_max_price_for_products("ad") == -1 print("All tests passed (Trie version).")