关于两段JavaScript算法时间复杂度分析的疑问

Hi there! Great job diving into time complexity analysis—let's go through your two code examples and validate your reasoning:

1. mySin Function Time Complexity #

You're absolutely correct that this function has a time complexity of O(n) (where n here refers to iterNum). Let's confirm with the code:

function mySin(x, iterNum) { 
  var mxx = -x*x; 
  var sin = 1; 
  var n = 0; 
  var term = 1; 
  for (var i = 1; i <= 2*iterNum; i++) { 
    n = n + 2; 
    term = term * mxx / ( n*(n+1) ); 
    sin = sin + term 
  } 
  sin = x*sin; 
  console.log(sin + " = my function."); 
  console.log(Math.sin(x) + " math.sin"); 
}

The core of this function is a single for loop that runs 2*iterNum times. Since constant factors don't affect asymptotic time complexity, this simplifies to O(iterNum)—or O(n) if we treat iterNum as our input size n. All other operations inside and outside the loop are constant-time (O(1)), so they don't change the overall complexity.

2. calculateFibonacciSum Function Time Complexity #

Your analysis here is spot-on too—this memoized Fibonacci function has a time complexity of O(n). Here's why:

function calculateFibonacciSum (num) { 
  if(cachedNumbers[num]) { 
    return cachedNumbers[num]; 
  } 
  if(('number' === typeof num) && num <= 0) { 
    throw new Error ('Fibonnci series starts with 0. Please, enter any interget greater than or equal to 0'); 
  } else if(('number' === typeof num) && num === 0) { 
    return 0; 
  } else if(('number' === typeof num) && (num === 1 || num === 2)) { 
    return 1; 
  } else { 
    var value = calculateFibonacciSum(num-1) + calculateFibonacciSum(num-2); 
    cachedNumbers[num] = value; 
    return value; 
  } 
}

• All the initial if/else checks are constant-time (O(1)) since they just verify conditions and return values immediately.
• The game-changer here is memoization (using cachedNumbers to store computed values). Without memoization, a naive recursive Fibonacci function would have O(2^n) time complexity due to exponential redundant calculations. But with caching, each number from 0 to num is computed exactly once. Once a value is stored in cachedNumbers, subsequent calls for that number just return the cached value in O(1) time. This cuts the total operations down to linear time—O(n).

Nice work on your analysis—you've nailed both cases!

内容的提问来源于stack exchange，提问作者QGuy123