Какова сложность этих методов словаря? - PullRequest
Новая
       7

Какова сложность этих методов словаря?

16 голосов
/ 23 сентября 2011

Может кто-нибудь объяснить, в чем сложность следующих Dictionary методов? 

ContainsKey(key)
Add(key,value);

Я пытаюсь выяснить сложность метода, который я написал: 

public void DistinctWords(String s)
{
    Dictionary<string,string> d = new Dictionary<string,string>();
    String[] splitted = s.split(" ");
    foreach ( String ss in splitted)
    { 
        if (!d.containskey(ss))
            d.add(ss,null);
    } 
}

Я предположил, что 2 словарных метода имеют сложность log (n), где n - количество ключей в словаре. Это правильно?

Ответы [ 6 ]

27 голосов
/ 23 сентября 2011

Это написано в документации для Словарь ...

Универсальный класс Dictionary обеспечивает сопоставление набора ключей с набором значений. Каждое дополнение к словарю состоит из значения и связанного с ним ключа. Извлечение значения с использованием его ключа выполняется очень быстро, близко к O (1), поскольку класс Dictionary реализован в виде хеш-таблицы.

А для функции Добавить :

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

13 голосов
/ 23 сентября 2011

Оба метода имеют постоянную сложность:

  • ContainsKey (ключ) - O (1)
  • Добавить (ключ, значение) - O (1)
11 голосов
/ 23 сентября 2011

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

Это потому, что Dictionary.Contains и Dictionary.Add обе (обычно) O (1) операции.

(Это немного сложнее, чем Dictionary.Add может быть O (n) для n элементов в Словаре, но только когда емкость словаря мала. Таким образом, если вы строите свой словарь сдостаточно большой емкости на начальном этапе, это будет O (m) для m строковых записей.)

При этом, если вы используете только Словарь для проверки существования, вы можете использовать HashSet<string>.Это позволит вам написать: 

  public void DistinctWords(String s)
  {
     HashSet<string> hash = new HashSet<string>(s.Split(' '));

     // Use hash here...

Поскольку ваш словарь является локальной переменной и не сохраняется (по крайней мере, в вашем коде), вы также можете использовать LINQ: 

 var distinctWords = s.Split(' ').Distinct();
7 голосов
/ 23 сентября 2011

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

2 голосов
/ 23 сентября 2011

Методы ContainsKey и Add близки к O (1).

Содержит ключевую документацию:

Этот метод приближается к операции O (1).

Добавить документацию:

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

Если вы используете Framework 3.5 или новее, вы можете использовать HashSet<T> вместо словаря с фиктивными значениями: 

public void DistinctWords(String s) {
  HashSet<string> d = new HashSet<string(s.split(" "));
}
2 голосов
/ 23 сентября 2011

Оба постоянных времени:

http://msdn.microsoft.com/en-us/library/kw5aaea4.aspx

http://msdn.microsoft.com/en-us/library/k7z0zy8k.aspx

Одна оговорка, однако:

"Если число меньше емкости, этот метод приближается к операции O (1). Если емкость должна быть увеличена для размещения нового элемента, этот метод становится операцией O (n), где n - это число."

...