Вычислите число Фибоначчи

Решение

Числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... Каждое число = сумма двух предыдущих. F(n) = F(n-1) + F(n-2)

Подход 1: Простая рекурсия (неоптимальная)

function fibonacci(n: number): number {
  if (n < 0) throw new Error("n must be non-negative");
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Примеры:
console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765

Проблема: Экспоненциальная сложность O(2^n)

fibonacci(5) вызывает:
              fib(5)
            /       \
         fib(4)     fib(3)
        /    \       /    \
     fib(3) fib(2) fib(2) fib(1)
     /  \    / \    / \
  fib(2) fib(1) fib(1) fib(0) ...
  / \
...

Много дублирующихся вычислений! fib(3) вычисляется 2 раза, fib(2) - 3 раза

Подход 2: Мемоизация (O(n) время)

function fibonacciMemo(n: number): number {
  const memo: Record<number, number> = {};
  
  function fib(n: number): number {
    if (n < 0) throw new Error("n must be non-negative");
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    // Проверяем кэш
    if (memo[n] !== undefined) {
      return memo[n];
    }
    
    // Вычисляем и кэшируем
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
  }
  
  return fib(n);
}

// Примеры:
console.log(fibonacciMemo(0));  // 0
console.log(fibonacciMemo(10)); // 55
console.log(fibonacciMemo(50)); // быстро!

Анализ:

• Временная сложность: O(n) вместо O(2^n)
• Пространственная сложность: O(n) для кэша + O(n) стека
• 50-й элемент считается за миллисекунды вместо минут

Подход 3: Итеративный (самый оптимальный)

function fibonacciIterative(n: number): number {
  if (n < 0) throw new Error("n must be non-negative");
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  let prev = 0;
  let curr = 1;
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

// Примеры:
console.log(fibonacciIterative(0));  // 0
console.log(fibonacciIterative(10)); // 55
console.log(fibonacciIterative(100)); // 354224848179261915075

Анализ:

• Временная сложность: O(n)
• Пространственная сложность: O(1) — только 2 переменные!
• Самая быстрая и эффективная

Подход 4: С деструктуризацией (компактно)

function fibonacciCompact(n: number): number {
  let [a, b] = [0, 1];
  
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  
  return a;
}

Подход 5: BigInt для больших чисел

function fibonacciBigInt(n: number): bigint {
  if (n < 0) throw new Error("n must be non-negative");
  if (n === 0) return 0n;
  if (n === 1) return 1n;
  
  let [a, b] = [0n, 1n];
  
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  
  return b;
}

// Примеры:
console.log(fibonacciBigInt(100));
// 354224848179261915075n

console.log(fibonacciBigInt(1000));
// очень большое число, не переполнится

Подход 6: Матричное возведение в степень (O(log n))

Фибоначчи можно вычислить через матричную степень:

[F(n+1)  F(n)  ]   [1 1]^n
[F(n)    F(n-1)] = [1 0]

function fibonacciMatrix(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  function multiply(a: number[][], b: number[][]): number[][] {
    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]],
    ];
  }
  
  function matrixPower(mat: number[][], p: number): number[][] {
    if (p === 1) return mat;
    
    const half = matrixPower(mat, Math.floor(p / 2));
    const result = multiply(half, half);
    
    if (p % 2 === 1) {
      return multiply(result, mat);
    }
    
    return result;
  }
  
  const base = [[1, 1], [1, 0]];
  const result = matrixPower(base, n);
  
  return result[0][1];
}

Анализ: O(log n) время, но на практике медленнее для малых n

Производительность: Сравнение

fibonacci(40):
- Простая рекурсия: ~1 секунда (2^40 вызовов)
- Мемоизация: ~0.001 мс
- Итеративная: ~0.0001 мс
- Матрица: ~0.01 мс

fibonacci(100):
- Простая рекурсия: невозможно (бесконечно)
- Мемоизация: ~0.1 мс
- Итеративная: ~0.01 мс
- Матрица: ~0.05 мс

Тестирование

const testCases = [
  [0, 0],
  [1, 1],
  [2, 1],
  [3, 2],
  [4, 3],
  [5, 5],
  [10, 55],
  [20, 6765],
];

testCases.forEach(([n, expected]) => {
  const result = fibonacciIterative(n as number);
  console.log(`fib(${n}) = ${result}, expected ${expected} ${result === expected ? '✓' : '✗'}`);
});

Сравнение подходов

Почему мемоизация спасает?

fib(5) с кэшем:
              fib(5)
            /       \
         fib(4)     fib(3) [кэш]
        /    \
     fib(3)   fib(2)
     [кэш]

Каждый результат вычисляется только один раз!

Рекомендация для интервью

Начните с итеративного подхода — это показывает лучшее понимание:

• O(1) памяти
• O(n) времени
• Практичность

Тогда упомяните:

• Рекурсия: интуитивнее, но экспоненциальная сложность
• Мемоизация: спасает рекурсию до O(n)
• Матрица: O(log n) для очень больших n

Ключевые моменты:

• Простая рекурсия неэффективна из-за дублирующихся вычислений
• Мемоизация переводит O(2^n) в O(n)
• Итерация лучше рекурсии для Фибоначчи
• Для результатов > 10^15 используй BigInt