用示例的Javascript代码讲O（1）空间复杂度是多少

Question

例如，我在下面提到了功能的输入和输出 reverseWords()

这是一个简单的示例，但这将有助于我理解。我如何为下面的请求编写O（1）空间中的函数？

// var input = ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r'];
// Output(same array): ['o', 'l', 'l', 'e', 'H', ' ', 'r', 'o', 'w']


// In O(1) space complexity 
function reverseWords(input) {

}

reverseWords(input);

我将如何编写O（1）空间中的函数？例如 -

function reverseString(str) {
    return str.split('').reverse().join('');;
}

reverseString("hello world");

这是O（1）空间复杂度吗？我已经提到了这是什么O（1）空间复杂度？但在对javascript的实际理解方面仍然存有疑问。

Answer 1

简单地说，O(1) 空间复杂度意味着除了传入的值之外，您仅使用恒定量的内存来生成结果。

例如，如果您在变量中仅使用单个原始值，那么这将是一个常数（因为无论您的输入有多大，它的数量都是相同的）

如果您的算法从分配与输入一样大的数组开始，那么它不会是 O(1)，而是 O(n)（因为输入越大，内存/空间要求就越大）。

因此，只要您确保您的算法永远不会分配空间要求取决于输入大小的任何内容，那么您的算法就有 O(1) 空间要求。

您在此答案中看不到任何特定于 JavaScript 的内容的原因是大 O 表示法几乎独立于所使用的底层技术。每种语言都有某种方法来分配可变长度的东西（例如作为数组的字符串）和固定长度的东西（“简单”值，例如数字和布尔值）。