Как рассчитать временную сложность этой функции, которая проверяет, имеет ли строка все уникальные символы?

Question

В книге «Cracking the Coding Interview», и этот Stack Overflow question обсуждает функцию, которая определяет, содержит ли строка все уникальные символы. Ответ на книгу, который использует смещение бит, находится в вопросе (см. Главный ответ на странице), и я не буду повторять его здесь.

Ответ Java имеет сложность O (N), и я не могу понять, что означает O (N). Я действительно хочу узнать, какова временная сложность этой реализации, которую я написал только сейчас. Это O (N)? Как определить сложность?

static void Main(string[] args) 
    { 
     string stringToCheck ; 
     bool hasAllUniqueChars = false; 
     stringToCheck = "Test"; 

     hasAllUniqueChars = CheckForUniqueChars(stringToCheck); 

     Console.WriteLine("String is Unique {0}", hasAllUniqueChars); 
     Console.Read(); 
    } 

    private static bool CheckForUniqueChars(string stringToCheck) 
    { 
     for (int i = 0; i < stringToCheck.Length - 1; i++) 
     { 
      for (int j = i; j < stringToCheck.Length - 1; j++) 
      { 
       if (Char.ToUpper(stringToCheck.ElementAt(i)) == 
        Char.ToUpper(stringToCheck.ElementAt(j+1))) 
       { 
        return false; 
       } 
      } 
     } 
     return true;   

    } 

Это возвращает ложь для теста, теста, Привет, и верно для Супермена, SpiderMan и губок и работает отлично.

Спасибо

Answer 1

Обозначение O (N) называется Big O Notation.Он обеспечивает верхнюю границу количества (примитивных) операций, которые требуется алгоритму относительно размера его ввода. Размер ввода часто обозначается как N.

Если количество примитивных операций не зависит от размера ввода, то сложность алгоритма равна O (1) или постоянному времени.

Если количество примитивных операций растет линейно по мере роста N (т. Е. Когда N удваивается, так же как и количество операций), то временная сложность линейна или O (N).

В вашем примере, верхняя граница, как представляется, O (N^2) для случайного читателя:

for (each item in input) 
    for (each item in input) 
    // do something 

Если N удваивается, количество операций четверок.

Однако, поскольку временная сложность ElementAt является линейной и не постоянной, сложность на самом деле O (N^3).

Answer 2

Edit: Это O (N^3), или пропорционально росту до полинома третьего порядка, в соответствии с предложениями других пользователей. Это связано с тем, что ElementAt() проходит через строку.

Ключом к этой сложности является ваша итерация. Эта структура:

for (each item in this thing) 
{ 
    for(each item in this thing) 
    { 
     if (iterate through this thing to check a condition) 
    } 
} 

Будет иметь порядок роста, пропорциональный полиному третьего порядка. Это не так, как bad, как и другие подпрограммы, так как внутренняя итерация по внутреннему циклу уменьшается по мере увеличения, но вы все еще выполняете итерацию для каждого элемента строки и итерации по строке для каждой из этих итераций. Скорее всего, если ваш алгоритм O (n^3), вы могли бы отредактировать его.

Sans ElementAt() звонок, он очень похож на Selection Sort с тем, как он итерации, если вам интересно.

Answer 3

Ваш алгоритм O (N^2), или быть более точным - может быть O (N^2). Может быть, потому что сейчас это O (n^3).

ElementAt() метод О (п) на IEnumerable, так потому, что он выполняется в течение двух вложенных циклов всего метода является O (N^3).

Вы можете сделать это O (N^2) путем преобразования string с на char[] перед тем петлями и с использованием массива индексатор вместо метода ElementAt расширения:

private static bool CheckForUniqueChars(string stringToCheck) 
{ 
    var chars = stringToCheck.ToCharArray(); 
    for (int i = 0; i < stringToCheck.Length - 1; i++) 
    { 
     for (int j = i; j < stringToCheck.Length - 1; j++) 
     { 
      if (Char.ToUpper(chars[i]) == Char.ToUpper(chars[j+1])) 
      { 
       return false; 
      } 
     } 
    } 
    return true;   
} 

Bonus: другой O (n) подход (поскольку HashSet<T> поиск O (1)):

private static bool CheckForUniqueChars(string stringToCheck) 
{ 
    var characters = new HashSet<char>(); 

    foreach (var character in stringToCheck) 
     if (!characters.Add(character)) 
      return false; 

    return true; 
} 

Answer 4

Не ответ на O (?)

Но это близко к O (N), как HashSet должен быть близок к O (1) для этого.
Примечание. HashSet.Count - O (1).

HashSet<char> chars = new HashSet<char>(); 
string password = "password"; 
Int32 count = 0; 
char cUpper; 
foreach (char c in password) 
{ 
    count++; 
    cUpper = char.ToUpper(c); 
    if (!chars.Add(char.ToUpper(c))) 
    { 
     System.Diagnostics.Debug.WriteLine("not uniue"); 
     break; 
    } 
} 
if(count == chars.Count) System.Diagnostics.Debug.WriteLine("uniue"); 

+1 Не видел, что Марцин был этот ответ минус ToUpper
ToUpper лучше использовать, чем TOLOWER, но я забыл, почему
Строка имеет регистрозависимости сравнение, но символ не