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

Может ли кто-нибудь объяснить, в чем сложность следующих методов 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 - количество ключей в словаре. Правильно ли это?

Ответы

Ответ 1

Эта процедура, в целом, является, по сути, временной сложностью 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();

Ответ 2

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

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

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

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

Ответ 3

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

  • ContainsKey (ключ) - O (1)
  • Добавить (ключ, значение) - O (1)

Ответ 4

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

Ответ 5

Оба являются постоянными:

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

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

Одно предупреждение:

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

Ответ 6

Метод 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(" "));
}