问题集：Algorithm

斐波那契数列有多少种解法+时间空间复杂度?

The Fibonacci sequence (each number = sum of two preceding ones: F(n) = F(n-1) + F(n-2)) has multiple solutions with varying time/space complexities:

(1) Recursive (Naive)

• Time: $O(2^n)$ – Exponential due to repeated calculations.
• Space: $O(n)$ – Call stack depth.
• Code:

  def fib(n):
      return n if n <= 1 else fib(n-1) + fib(n-2)

(2) Memoization (Top-Down DP)

• Time: $O(n)$ – Each of n values computed once.
• Space: $O(n)$ – Storage for cache + call stack.
• Code:

  def fib(n, memo={}):
      if n not in memo:
          memo[n] = n if n <= 1 else fib(n-1) + fib(n-2)
      return memo[n]

(3) Iterative (Bottom-Up DP)

• Time: $O(n)$ – Single loop.
• Space: $O(1)$ – Constant space (store only last two values).
• Code:

  def fib(n):
      a, b = 0, 1
      for _ in range(n):
          a, b = b, a + b
      return a

(4) Matrix Exponentiation

• Time: O(log n) – Fast doubling via matrix power.
• Space: O(1) – No extra storage.
• Code: (Requires matrix math implementation)

(5) Closed-Form (Binet’s Formula)

• Time: O(1) – Direct computation (floating-point precision limits).
• Space: O(1).
• Formula:
  

第k大的数有多少种解法+时间空间复杂度?

(1) Sorting

• Time: $O(n \log n)$ – Sorting dominates.
• Space: O(1) if in-place (e.g., sorted(nums)[-k]).

(2) Max-Heap (Priority Queue)

• Time: $O(n + k log n)$ – Heapify (O(n)) + k extractions.
• Space: O(n) – Heap storage.
• Code:

  import heapq
  def find_kth_largest(nums, k):
      return heapq.nlargest(k, nums)[-1]

(3) Quickselect (Hoare’s Algorithm)

• Time: Average $O(n)$, Worst $O(n^2)$ – Like quicksort but recurses on one side.
• Space: $O(1)$ – In-place partitioning.
• Code: (Lomuto or Hoare partition scheme)

(4) Counting Sort (For Small Integer Ranges)

• Time: O(n + range) – Linear if range is bounded (e.g., 0-100).
• Space: O(range) – Frequency array.

(5) BST/Ordered Structure

• Time: O(n log k) – Maintain a size-k BST (e.g., bisect in Python).
• Space: O(k).

Summary:

• For Fibonacci, prefer iterative (O(n) time, O(1) space) or matrix (O(log n)) for large n.
• For Kth Largest, quickselect is fastest on average, while heap is more stable.