JavaScript算法时间复杂度判断：三个算法的疑问求助

嘿，我来帮你理清这三个算法的时间复杂度问题，逐个拆解分析：

1. 平方根求解算法 #

先修正下你代码里的语法问题（原代码漏了do-while的闭合和精度判断条件），正确的牛顿迭代实现大概是这样：

function sqrt(num) {
  let guess = num / 3;
  let lastGuess;
  do {
    lastGuess = guess;
    guess = (num / guess + guess) / 2;
  } while (Math.abs(lastGuess - guess) > 1e-9); // 设定一个精度阈值
  return guess;
}

你的判断O(n)是错误的。这是经典的牛顿迭代法求平方根，它的收敛速度非常快：每次迭代后，近似值的误差会以平方级缩小——简单说就是有效位数翻倍。比如从初始猜测到达到常规精度（比如1e-9），只需要5-10次循环，这个次数和输入num的大小几乎无关，哪怕num是10^18这样的大数，循环次数也不会线性增长。

所以它的时间复杂度是O(1)（常数时间），更严谨的表述是O(log log num)，但绝对不是线性的O(n)。

2. 数组最大值递归求解算法 #

先整理下代码：

function max(numArray) {
  // copy the given array
  let nums = numArray.slice();
  // base case: if we're at the last number, return it
  if (nums.length == 1) {
    return nums[0];
  }
  // check the first two numbers in the array and remove the lesser
  if (nums[0] < nums[1]) {
    nums.splice(0, 1);
  } else {
    nums.splice(1, 1);
  }
  // with one less number in the array, call the same function
  return max(nums);
}

你的判断O(n)是错误的，实际时间复杂度是O(n²)。问题出在splice操作上：JavaScript数组是基于连续内存的，当你用splice删除非末尾元素时，需要把该位置后面的所有元素向前移动一位，这个操作的时间复杂度是O(k)，其中k是当前数组的长度。

我们来算总开销：第一次调用时数组长度为n，splice需要O(n)时间；第二次数组长度n-1，splice需要O(n-1)；直到最后一次数组长度为2，splice需要O(2)。总时间是n + (n-1) + ... + 2 = (n² +n -2)/2，属于O(n²)的量级。

如果想优化到O(n)，可以不用每次复制数组和修改数组结构，比如用递归时传递起始/结束索引，或者直接遍历数组找最大值，避免数组元素移动的开销。

3. 自定义正弦函数算法 #

整理后的代码：

function mySin(x, iterNum) {
  const mxx = -x*x;
  let sin = 1;
  let n = 0;
  let term = 1;
  for (let 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");
}

你的判断是正确的，时间复杂度为O(iterNum)，也就是线性的O(n)（这里的n对应输入参数iterNum）。因为循环执行了2*iterNum次，每次循环里的算术运算都是常数时间O(1)，总时间和iterNum呈严格的线性关系。

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