有人能给我解释一下我写的leetcode解决方案的空间复杂性吗？

Question

我觉得它在这个场景中甚至不那么重要，但我想要对它有一个强有力的基础理解。

当使用像filter或map这样的函数来操作字符串和类似的数据时，这是否会将空间复杂度增加到o(N)？

在下面的解决方案的情况下，空间复杂度是否为O(1)？

最后，有没有可能出现O(N^2)的空间复杂度？

// BACKSPACE COMPARE  (DATA-STRUCTURE STRING/ARRAY)

/*
Given two strings S and T, return if they equal when both are typed out.
ANy '#' that appears in the string counts as a backspace
*/

const backspaceCompare = (s, t) => {
    /*
    turn strings into an array
    see if the array has an '#'
    if it does, filter out '#' and the number before it
    compare the two arrays after and see if they're equal
    */

    // this filters out a '#' and deletes the previous item each time it's called
    const filteringFunc = (arr, index1, index2) => {
            const arrFiltered = arr.filter((val, index) => {
               return index !== index1 && index !== index2;
            });
            return arrFiltered;  
    };
    
    // change the strings to arrAYS because filter function only works on arrays
    let sArr = s.split('');
    let tArr = t.split('');

    // while there's a '#' this function will call the filter function and filter out each instance of '#' as well as its previous index
    const eradicateHash = (arr) => {
        while(arr.includes('#')){
            const removeThis = arr.indexOf('#');
            const andThis = removeThis - 1;
            arr = filteringFunc(arr, removeThis, andThis);
        };
        return arr;
    };
    // calling the function on the arrays
    sArr = eradicateHash(sArr);
    tArr = eradicateHash(tArr);
    
    // after arrays have been filtered it has to be changed to a stirng because arrays by themselves cannot be compared to other arrays
    sArr = sArr.toString();
    tArr = tArr.toString();

    // returning via the ternary operator
    return tArr === sArr ? true : false;
};

​

Answer 1

您在这里遇到的问题(在任何其他真实世界的示例中都会遇到)：

• 什么是太空？你有没有计算内存，磁盘上的文件，寄存器？现代计算机本质上是复杂的，你不会找到一个明确的定义来定义什么是空间。

，

• ，什么是输入？如果你把一个数组作为我们函数的参数，然后把无数个项目推给它，你的算法仍然是O(1)吗，因为它只增加了输入？如果不是，你的算法有什么不同？那么引用呢?传入一个引用(具有固定大小)是否总是n=1，或者是否将数组引用的大小作为n?

考虑到这两个无法回答的问题，我们基本上可以说你的算法的空间复杂度是O(1)，o(n)或其他任何东西，因为你总是可以以某种方式争论这是对还是错，这根本没有用。

相反，让我们退后一步，看看理论计算机科学DSPACE中定义的具体计算资源。DSPACE描述了工作带上的单元数相对于确定性图灵机²的输入带的数量。由于其他空间资源是相当理论的(例如NSPACE，非确定性图灵机将占用的空间)，可以说DSPACE对于所有现实世界的使用都是空间复杂性。现在，如果我们看一台图灵机，我们避免了上面的问题，因为空间定义得很清楚(每个单元都有一个字母表的字符，所以磁带的长度是一个整数)，输入的定义也很清楚，因为我们将输入磁带从工作磁带中分离出来。输入磁带的长度称为n，我们搜索工作磁带的大小。

现在，为了证明你的算法在DSPACE(O(n))或DSPACE(O(1))中，你必须将你的程序重新表述为图灵机。这实际上是一个有趣的练习，尽管我们实际上可以通过观察您所做的观察来简化这一步骤：“他们只是将值重置为更小的值”，或者换句话说，算法获取两个长度为m和l的字符串，并修改它们，直到所有#都被删除。然后对它们进行比较。现在，假设我们实际上不能修改输入磁带(它是只读的)，在图灵机中，作为第一步，我们必须将所有符号从输入磁带复制到工作磁带。我们也许能够以这样的方式构建机器，即在复制时删除#，但是其中可能仍然有一个没有#的输入，然后我们将整个输入复制到工作磁带中。这意味着工作磁带必须与输入磁带一样大，或者换句话说：

L ∈ DSPACE(n) = DSPACE(O(n))

O(n)现在作为你的问题的答案是否有用是很有争议的，因为我们不是在图灵机上运行的。

现在来回答你的其他问题：

当使用像过滤器或映射这样的函数来操作字符串和类似的数据时，这是否会将空间复杂度增加到o(N)？

是。在图灵机中，过滤器和映射都必须将输入磁带复制到工作磁带中。

，最后，有没有可能出现O(N^2)的空间复杂度？

没有被图灵机访问的工作带中的细胞是无用的，因此图灵机至少会做和它有细胞一样多的步骤。因此，时间复杂度总是比空间复杂度更差。因此，你可以在DTIME(O(n²))中找到很多算法(比如冒泡排序)，它们也在DSPACE(O(n))中。因此，要找到DSPACE(O(n²))中的算法，您必须查看其时间复杂度更差的算法，这使得它们对现实世界的应用程序用处较小。所以，是的，你不太可能在DSPACE中遇到一个算法(O(n²))

²要获得图灵机的感觉，请使用此Google Doodle