这些Dictionary方法的复杂性是什么?

本文关键字：是什么复杂性 Dictionary 方法这些 | 更新日期: 2023-09-27 18:09:34

谁能解释一下以下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);
    } 
}

我假设这两个字典方法的复杂度为log(n)，其中n是字典中的键数。这是正确的吗?

这些Dictionary方法的复杂性是什么?

这是在Dictionary的文档中写的…

Dictionary泛型类提供从一组键到一组值的映射。每个向字典中添加的内容都由一个值及其关联的键组成。通过使用键来检索值非常快，接近于0(1)，因为Dictionary类是作为散列表实现的。

对于Add函数:

如果Count小于capacity，该方法接近O(1)操作。如果必须增加容量以容纳新元素，则该方法变为O(n)操作，其中n为Count。

两种方法的复杂度都是恒定的:

ContainsKey(key) - O(1)
添加(键，值)- 0 (1)

作为一个整体，这个例程的时间复杂度实际上是0 (m)，其中m是搜索中字符串的数量。

这是因为字典。包含和字典。加法(通常)都是O(1)操作。

(它比这稍微复杂一点，如Dictionary)。对于字典中的n个条目，Add可以为O(n)，但仅在字典容量较小的情况下。因此，如果您预先用足够大的容量构建字典，那么对于m个字符串条目，它将是O(m)。

也就是说，如果您只使用Dictionary进行存在性检查，则可以使用HashSet<string>。你可以这样写:

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

由于字典是一个局部变量，并且没有存储(至少在代码中)，因此还可以使用LINQ:

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

这是不正确的，通常字典/哈希表查找是O(1)。为了做到这一点，它将从你正在寻找的键生成一个哈希，并且只将它与具有相同哈希值的项进行比较-对于一个好的哈希算法，这被认为是O(1)总体(平摊O(1) -只有在极少数情况下，容量必须增加，你有O(n))。

都是常量时间:

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。"

ContainsKey和Add方法接近0(1)。

ContainsKey文档:

此方法接近于O(1)操作。

添加文档:

如果Count小于容量，该方法趋于0 (1)操作。如果容量必须增加以适应新的元素时，此方法变为O(n)操作，其中n为Count。

如果你使用的是框架3.5或更高版本，你可以使用HashSet<T>而不是一个带有虚拟值的字典:

public void DistinctWords(String s) {
  HashSet<string> d = new HashSet<string(s.split(" "));
}

相关文章：

最新信息: