Насколько пространственная сложность этого алгоритма равна O (1)

Question

Я нашел алгоритм здесь , чтобы удалить повторяющиеся символы из строки с O (1) пробелом сложности (SC).Здесь мы видим, что алгоритм преобразует строку в массив символов, который не является постоянным, он будет меняться в зависимости от размера ввода.Они утверждают, что он будет работать в SC O (1).Как?

// 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

Я нашел алгоритм здесь, чтобы удалить повторяющиеся символы из строки с O (1) пробелом сложности (SC).Здесь мы видим, что алгоритм преобразует строку в массив символов, который не является постоянным, он будет меняться в зависимости от размера ввода.Они утверждают, что он будет работать в SC из O (1).Как?

Это не так.

Алгоритм принимает в качестве входных данных строку произвольного размера, состоящую только из 26 символов, и, следовательно, выходной результат составляет всего 26 символов или менее, поэтомувыходной массив не обязательно должен иметь размер входных данных.

Вы правильно заметили, что реализация, представленная на сайте, выделяет O (n) дополнительного пространства без необходимости для массива char.

Упражнение : Можете ли вы исправить проблему с массивом символов?

Более сложное упражнение : Можете ли вы описать и реализовать структуру данных строки, которая эффективно реализует контракт строки, нопозволяет этот алгоритм быть реализованным на самом деле, используя только O (1) дополнительное пространство для произвольных строк?

Лучшее упражнение : тот факт, что мы ограничены алфавитом из 26 символов, это то, что позволяетДрянное решение «давайте просто использовать int как набор флагов».Вместо того, чтобы говорить, что n - это размер входной строки, что если мы допустим произвольные последовательности произвольных значений, которые имеют отношение равенства ;Можете ли вы найти решение этой проблемы, которое заключается в O (n) по размеру выходной последовательности, а не входной последовательности?

То есть, вы можете реализовать public static IEnumerable<T> Distinct<T>(this IEnumerable<T> t) таким образом, чтобы вывод был дедуплицированно в остальном в том же порядке, что и вход, с использованием памяти O (n), где n - размер выходной последовательности?

Это лучшее упражнение, поскольку эта функция фактически реализована в базовом классе.библиотека .Это полезно, в отличие от задачи с игрушкой.

Я также отмечаю, что в постановке задачи предполагается, что существует только один соответствующий алфавит с символами в нижнем регистре, и что их 26.Это предположение неверно.