c# - 这个算法的空间复杂度是多少O(1)

Question

我找到了一个算法 here从具有 O(1) 空间复杂度 (SC) 的字符串中删除重复字符。这里我们看到算法将字符串转换为字符数组，这不是常量，它会根据输入大小而变化。他们声称它将在 O(1) 的 SC 中运行。如何？

// Function to remove duplicates 
static string removeDuplicatesFromString(string string1) 
{ 

    // keeps track of visited characters 
    int counter = 0; 
    char[] str = string1.ToCharArray(); 
    int i = 0; 
    int size = str.Length; 

    // gets character value 
    int x; 

    // keeps track of length of resultant String 
    int length = 0; 

    while (i < size) { 
        x = str[i] - 97; 

        // check if Xth bit of counter is unset 
        if ((counter & (1 << x)) == 0) { 

            str[length] = (char)('a' + x); 

            // mark current character as visited 
            counter = counter | (1 << x); 

            length++; 
        } 
        i++; 
    } 

    return (new string(str)).Substring(0, length); 
} 

看来我不明白空间复杂度。

Answer 1

I found an algorithm here to remove duplicate characters from string with O(1) space complexity (SC). Here we see that the algorithm converts string to character array which is not constant, it will change depending on input size. They claim that it will run in SC of O(1). How?

它没有。

该算法将仅由 26 个字符组成的任意大小的字符串作为其输入，因此输出仅为 26 个字符或更少，因此输出数组不需要为输入的大小。

您正确地指出网站上给出的实现为 char 数组不必要地分配了 O(n) 的额外空间。

练习:你能解决字符数组问题吗？

较难的练习:您能否描述和实现一个字符串数据结构，该结构可以有效地实现字符串的契约，但实际上仅使用任意字符串的 O(1) 额外空间就可以实现该算法？

更好的练习:我们被限制在 26 个字符的字母表这一事实使得俗气的“让我们只使用一个 int 作为一组标志”解决方案成为可能。如果我们允许具有相等关系的任意值的任意序列，而不是说 n 是输入字符串的大小；你能想出一个输出序列大小为 O(n) 而不是输入序列的解决方案吗？

也就是说，你能实现public static IEnumerable<T> Distinct<T>(this IEnumerable<T> t)吗？使得输出被去重但在其他方面与输入的顺序相同，使用 O(n) 存储，其中 n 是输出序列的大小？

这是一个更好的练习，因为这个函数实际上是在基类库中实现的。它很有用，不像玩具问题。

我还注意到，问题陈述假设只有一个相关的小写字母表，并且有 26 个。这个假设是错误的。