递归函数上的执行超时
我正在做最小可能和 Kata on CodeWars，它对大多数数组都很好，但是当算法正在处理非常大的数组时，我会陷入困境：
给定一个由正整数组成的X数组，它的元素将根据需要对它们运行以下操作： 如果Xi > Xj，则Xi = Xi - Xj 当不再可能进行转换时，返回其和(“最小可能和”)。 例如，输入
X = [6, 9, 21]元素的连续转换详细说明如下： X_1 = 6，9，12 # -> X_12 = X2 - X1 = 21 -9 X_2 = 6，9，6# -> X_22 = X_12 - X_1 = 12 -6 X_3 = 6，3，6# -> X_31 = X_21 -X_21- X_2 =9-6 X_4 = 6，3，3#X_4= -> -=6-3 en20#= 3，3，3# -> X_51 = X_4 - X_41 =6-3 返回的输出是最终转换的总和(在这里9)。
下面是我的递归解决方案：
const solution =(numbers) => {
//1. find bigger and smallest number in the array, and keep the index of the biggest number
let bigger = Math.max(...numbers)
let smaller = Math.min(...numbers)
let index = numbers.findIndex((n)=> n === bigger)
//2. return the result if the result of the subtraction is positive or null
if (smaller === bigger) {
return numbers.reduce((a,c) => a + c)
}
//3.substract and replace
numbers.splice(index, 1, bigger-smaller)
return solution(numbers)
}因此，我想知道解决方案中的哪个操作导致超时；哪一个是处理器循环使用的时间最多的？
回答 2
Stack Overflow用户
发布于 2021-04-22 16:00:56
解决方案的好处是，它认识到，当所有值都相同(smaller === bigger)时，应该计算和返回和。
但是，如果从最大的值减去最小的值以替换最大的值，这就不太好了。您有兴趣使这些值尽可能小，所以这是您可能做出的最糟糕的选择。使用任何其他对作为减法已经是一个改进。
另外：
- 每次递归调用都必须扫描整个数组，这很费时。它使你的解决方案O(2)。
- 对于
findIndex在这里所能做的事情来说，indexOf确实(效率低下)过分了。 - 如果你已经决定用这对做减法，那为什么不考虑一下如果你尽可能多地减去，会发生什么呢？你可以从除法和余数的角度来考虑这意味着什么。
- 只需将递归调用替换为循环(
while (true))，就可以避免过多的堆栈使用。
为了找到更好的算法，想想当数组中只有2的时候，它意味着什么。这一定意味着原始输入中没有奇数。类似地，如果它是3，那么这意味着输入只包含被3除以3的数字。如果你继续这样做，你会注意到数组中的值是一个公共的除数。有了这个洞察力，你应该能够写一个更有效的算法。
Stack Overflow用户
发布于 2021-04-23 04:00:48
这是正确的做法！更短更有效率！
const gcd = (a, b) =>
b ? gcd(b, a % b) : a;
const solution = numbers =>
numbers.length * numbers.reduce(gcd);你是对的，正确的方法不是用欧几里德算法，而是用这种方法找出gcd。谢谢!！
https://stackoverflow.com/questions/67216032
复制相似问题
腾讯云开发者
