javascript - 简单 for 循环与 >> 运算符之间的区别

Question

我在 vue.js 中找到了这段代码。但是，使用 snippet-1 编写模板 repeat 与使用 snippet-2 相比有什么优势。

片段 - 1 - Source

const repeat = (str, n) => {
    let res = ''
    while (n) {
      if (n % 2 === 1) res += str
      if (n > 1) str += str
      n >>= 1
    }
    return res
  }

片段 - 2

const repeat = (str, n) => {
  let res = ''
  while (n--) {
    res += str;
  }
  return res
}

Answer 1

这是不同的迭代次数。

在第二个片段中，您有 n 次迭代。但在第一个片段中，您大致有 log n 次迭代。这意味着函数的复杂性从 O(n) 下降到 O(log n)，这对于巨大的 n 可能很重要。

它是如何工作的？作为初学者，这里以一种过于简单的方式总结了逻辑:如果我们将迭代减半，我们可以将添加到结果中的内容加倍。

所以 >> 1 有点像 整数除以 2。整数除法意味着 5/2 结果是 2。但这意味着我们错过了迭代!？

在每个奇数上，我们在将其加倍到结果之前添加当前字符串，因此我们在继续之前将迭代的总和(当前 str)保存在我们的结果中。因此，我们知道我们的迭代是保存的，我们通过将每一步剩余的迭代减半来向下迭代，同时将我们很快添加到结果中的内容加倍。

通过这种重复，我们跳过了很多迭代，这是降低复杂性的关键。

对于 n = 5:

1 'str: ' 'kk' 'res: ' 'k'
2 'str: ' 'kkkk' 'res: ' 'k'
3 'str: ' 'kkkk' 'res: ' 'kkkkk'

对于 n = 10:

1 'str: ' 'kk' 'res: ' ''
2 'str: ' 'kkkk' 'res: ' 'kk'
3 'str: ' 'kkkkkkkk' 'res: ' 'kk'
4 'str: ' 'kkkkkkkk' 'res: ' 'kkkkkkkkkk'

对于 n = 11

1 'str: ' 'kk' 'res: ' 'k'
2 'str: ' 'kkkk' 'res: ' 'kkk'
3 'str: ' 'kkkkkkkk' 'res: ' 'kkk'
4 'str: ' 'kkkkkkkk' 'res: ' 'kkkkkkkkkkk'