Tag: 复杂性理论

这些Dictionary方法的复杂性是什么？: 任何人都可以解释下面的Dictionary方法的复杂性是什么？ ContainsKey(key) Add(key,value); 我想弄清楚我写的方法的复杂性： public void DistinctWords(String s) { Dictionary d = new Dictionary(); String[] splitted = s.split(” “); foreach ( String ss in splitted) { if (!d.containskey(ss)) d.add(ss,null); } } 我假设2个字典方法具有log（n）复杂度，其中n是字典中的键数。它是否正确？

Dictionary.Keys返回的KeyCollection上的操作有多快？（。净）: IDictionary定义方法IDictionary.ContainsKey(in TK)和属性IDictionary.Keys （在ICollection类型中）。我对IDictionary Dictionary实现中此方法和属性的（渐近）复杂性感兴趣。考虑定义 IDictionary dict = new Dictionary(); int k = new Random().Next(); 并且考虑到我们已经在字典中添加了唯一的KeyValuePair 。调用dict.ContainsKey(k)预期（渐近）复杂度是多少？我希望它在O(1)但我没有在Dictionary.ContainsKey文档中找到它。调用dict.Keys.Contains(k)预期（渐近）复杂度是多少？我希望它在O(1)但我没有在Dictionary.Keys文档中找到它，也没有在Dictionary.Keys文档中找到它。如果它在O(1)我不明白为什么IDictionary.Keys属性的类型是ICollection而不是ISet （例如在Java中）。

在尊重偏好的同时将人分配到建筑物？: 一位朋友今天问了我一个关于转让问题的问题。我找到了一个非常简单的解决方案，但我觉得它可以变得更简单，更快捷。非常感谢您的帮助。问题：假设我有N个人，我需要将它们分配到M个建筑物中，每个建筑物都可以容纳K个人。并非所有人都愿意相互生活，所以我有一个N * N细胞矩阵和一个标志着愿意相互生活的人的1。如果一个单元格包含1，则意味着我和J可以共存。显然，矩阵在主对角线周围是对称的。我的解决方案如下（伪代码）： int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize) { int[] freePeople = findFreePeople(people); if(freePeople) = 0 { return people; } foreach(int person in freePeople) { for(int buildingIndex=0 to numBuildings) { if( CheckIfPersonFitsInBuilding(…) ) { int[] tempPeople = people.Copy(); tempPeople[person] = buildingIndex; int[] result = […]

HashSet （IEqualityComparer ）的查找时间复杂度是多少？: 在C＃.NET中，我喜欢使用HashSets，因为它们的查找时间复杂度为O（1）。如果我要查询大量数据，我通常更喜欢将HashSet用于List，因为它具有这种时间复杂性。令我困惑的是HashSet的构造函数，它将IEqualityComparer作为参数： http://msdn.microsoft.com/en-us/library/bb359100.aspx 在上面的链接中，备注注意到“构造函数是一个O（1）操作”，但如果是这种情况，我很好奇，如果查找仍然是O（1）。特别是，在我看来，如果我要编写一个Comparer来传递给HashSet的构造函数，每当我执行查找时，必须在每个键上执行Comparer代码以检查是否存在一场比赛。这不是O（1），而是O（n）。当元素添加到集合中时，实现是否在内部构建查找表？总的来说，我如何确定有关.NET数据结构复杂性的信息？