请求解给定normalize算法的代价函数（时间复杂度）

问题背景 #

我花了数小时思考和谷歌搜索，仍无法确定如何求解该算法的代价函数，也不确定自己的思路是否正确，希望能获得更高效、简便的解题方法建议，感谢帮助！

待分析的算法代码 #

public float[] normalize (float[] seq) {
  int n = seq.length;
  float sum = 0;
  int cnt = 0;
  int i;
  for (i = 1; i < n; i = i + i ) {
    for ( int j = 0; j < i; j++) {
      sum = sum + seq [j];
    }
    cnt += i;
  }
  float[] res = new float [n];
  while (i >= 0) {
    if (i < n) {
      res [i] = seq[i] / (sum / cnt);
    }
  i--;
  }
  return res;
}

时间复杂度分析 #

思路纠正 #

你当前认为算法时间复杂度是O(n log n)，这个结论是错误的，正确的时间复杂度应为O(n)，详细分析如下：

• 外层for循环：i从1开始每次翻倍，直到i >= n停止，循环执行次数为log₂n次（比如n=8时，i取1、2、4，共3次，即log₂8=3）。
• 内层for循环：每次外层循环对应的内层执行次数等于当前i的值，总执行次数是等比数列求和：1 + 2 + 4 + ... + 2^k，其中2^k < n ≤ 2^(k+1)。求和结果为2^(k+1)-1，而2^(k+1) ≤ 2n，因此总操作数为O(n)。
• 后续while循环：i从首次超过n的值递减到0，其中i < n的部分执行n次赋值操作，总操作数为O(n)。

将各部分相加，总时间复杂度为O(n) + O(n) = O(n)。

简便解题方法建议 #

• 等比数列求和法：遇到循环变量翻倍/减半的场景，直接用等比数列求和公式计算总操作数，避免错误的“每次执行次数×循环次数”误区；
• 分阶段拆解：把算法拆分为多个独立阶段（如本例的求和阶段、归一化阶段），分别计算每个阶段的时间复杂度后再合并；
• 边界值验证：用小的n值（如n=4、n=8）手动计算循环执行次数，验证复杂度推导是否正确。

算法优化建议 #

原算法的求和阶段存在大量重复计算（每次内层循环都重新累加前i个元素），可以直接一次遍历完成求和，优化后代码如下：

public float[] normalize(float[] seq) {
    int n = seq.length;
    if (n == 0) return new float[0];
    
    float sum = 0;
    // 一次遍历完成求和，时间复杂度O(n)
    for (float num : seq) {
        sum += num;
    }
    // 避免除以0的边界情况
    float factor = sum != 0 ? n / sum : 0;
    
    float[] res = new float[n];
    for (int i = 0; i < n; i++) {
        res[i] = seq[i] * factor;
    }
    return res;
}

优化后的算法时间复杂度仍为O(n)，减少了重复计算，代码可读性更高，同时处理了sum为0的异常情况。

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