自定义除自身外数组乘积算法的时间与空间复杂度判定

你自己算的*时间复杂度O(n²)、空间复杂度O(n)*的结果是准确的，具体拆解如下：

时间复杂度 #

• 外层while循环会从头到尾跑满长度为n的输入数组，一共执行n轮，这部分开销是O(n)
• 每跑一轮外层循环，内层都会完整遍历整个输入数组算乘积，单轮内层遍历的开销是O(n)
• 两层循环是嵌套关系，总时间开销就是n乘O(n)，也就是O(n²)

这里提一句你代码的逻辑问题：内层循环用if i != nums[start]判断要跳过的元素是错的。题目要求是跳过当前遍历到的索引位置的元素，不是跳过所有值和当前位置相等的元素。如果数组里有重复值，比如输入[2,3,2]，处理第一个2的时候，你代码会把最后一个2也跳过，乘出来的结果只有3，和正确结果6差很多，跑不通测试用例。

空间复杂度 #

• 算法运行时额外申请的空间，核心是和输入数组等长的result列表，用来存最终要返回的结果，这部分空间占用和输入规模n是线性正相关的
• 剩下的start、total、循环临时变量i都是固定占一点空间的常数级变量，不会随着n变大而增加占用
• 所以整体额外空间复杂度确实是O(n)

小补充 #

这道题有更优的解法：可以不用嵌套循环，先从左到右跑一遍存前缀乘积，再从右到左跑一遍乘后缀乘积，能把时间复杂度降到O(n)，如果不算输出结果占的空间，额外空间能到O(1)，你之后可以试着改改。

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