面试题：JavaScript 复杂函数方法优化及性能分析

Question

有一个函数 `function complexCalculation(arr) { let result = []; for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (arr[i] % arr[j] === 0) { result.push(arr[i]); } } } return result; }`，该函数接收一个数组并进行复杂的计算。请优化这段代码，同时分析优化前后的时间复杂度和空间复杂度，并说明优化思路。

Answer 1

优化后代码

function complexCalculation(arr) {
    const set = new Set();
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] % arr[j] === 0) {
                set.add(arr[i]);
            }
        }
    }
    return Array.from(set);
}

时间复杂度分析

• 优化前：
  • 有两层嵌套的for循环，外层循环执行n次，内层循环也执行n次，每次循环都进行一次取模判断操作。所以时间复杂度为$O(n^2)$，其中n是数组arr的长度。
• 优化后：
  • 同样是两层嵌套的for循环，时间复杂度依旧是$O(n^2)$。但是优化后使用Set来存储结果，避免了重复元素的添加，在某些情况下实际运行时间会有所改善。

空间复杂度分析

• 优化前：
  • 空间复杂度主要取决于结果数组result。在最坏情况下，数组中的每个元素都满足arr[i] % arr[j] === 0，结果数组result的长度可能达到$n^2$，所以空间复杂度为$O(n^2)$。
• 优化后：
  • 使用Set来存储结果，由于Set不会存储重复元素，在最坏情况下，Set中最多存储n个不同的元素，所以空间复杂度为$O(n)$。

优化思路

• 原代码中result数组可能会存储大量重复元素，使用Set数据结构可以自动去重，避免重复存储相同的元素，从而降低空间复杂度。最后通过Array.from(set)将Set转换为数组返回，满足题目要求的返回形式。