什么是这些字典方法的复杂性？ [英] What is the complexity of these Dictionary methods?

问题描述

谁能解释什么是以下词典方法的复杂性？

Can anyone explain what is the complexity of the following Dictionary methods?

ContainsKey(key)
Add(key,value);

我试图找出一个方法，我写的复杂性：

I'm trying to figure out the complexity of a method I wrote:

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字典的方法是日志（ n）的复杂性，其中的 N 的是在字典中键的数量。这是正确的？

I assumed that the 2 dictionary methods are of log(n) complexity where n is the number of keys in the dictionary. Is this correct?

推荐答案

这个程序中，作为一个整体，是有效的，O（M）的时间复杂度，m为在搜索串的数量。

This routine, as a whole, is, effectively, O(m) time complexity, with m being the number of strings in your search.

这是成为的 Dictionary.Contains 和 Dictionary.Add 都（通常）O（1）操作。

This is become Dictionary.Contains and Dictionary.Add are both (normally) O(1) operations.

（它略比这更复杂，因为Dictionary.Add可以在字典n项为O（n），但仅当字典容量是小的。作为例如，如果你建立你的字典有足够大的容量达阵，这将是O（M）在m字符串项）

(It's slightly more complicated than that, as Dictionary.Add can be O(n) for n items in the Dictionary, but only when the dictionary capacity is small. As such, if you construct your dictionary with a large enough capacity up front, it would be O(m) for m string entries.)

这是说，如果你'。只重使用词典存在检查，你可以使用的HashSet<串GT; 。这将允许你写：

That being said, if you're only using the Dictionary for existence checking, you could use a HashSet<string>. This would allow you to write:

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

     // Use hash here...

由于你的字典是一个局部变量，而不是存储（至少在你的代码中），你也可以使用LINQ：

As your dictionary is a local variable, and not stored (at least in your code), you could also use LINQ:

 var distinctWords = s.Split(' ').Distinct();

这篇关于什么是这些字典方法的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！