Tag: 数据结构

哈希表运行时复杂性（插入，search和删除）: 为什么我在哈希表上看到这些函数的不同运行时复杂性？在维基上，search和删除是O（n）（我认为哈希表的重点是有恒定的查找，所以如果search是O（n），有什么意义）。在某些课程笔记中，我看到了一些复杂性，取决于某些细节，包括所有的O（1）。为什么如果我能得到所有的O（1），还有其他的实现呢？如果我在像C ++或Java这样的语言中使用标准哈希表，我可以期望时间复杂度是多less？

std :: vector与std :: list与std :: slist的相对性能？: 对于一个简单的链表来说，对列表元素的随机访问是不需要的，使用std::list而不是std::vector有什么显着的优点（性能或其他）如果需要向后遍历，在迭代元素之前使用std::slist和reverse()会更有效率吗？

如何在c＃中创build一个trie: 有谁知道我在哪里可以find一个如何在C＃中构build一个trie的例子。我正在尝试使用字典/单词列表并创build一个trie。

散列树结构: 我刚刚在我的项目中遇到了一个场景，我需要将不同的树对象与已知实例进行比较，并且认为某种在任意树上运行的哈希algorithm将非常有用。以下面的树为例： Ø / \ / \ OO / | \ | / | \ | OOOO / \ / \ OO 其中每个O表示树的一个节点，是一个任意的对象，有一个关联的散列函数。所以问题简化为：给定树结构节点的散列码和已知的结构，计算整个树的（相对）无碰撞散列码的体面algorithm是什么？有关散列函数属性的一些说明：散列函数应该取决于树中每个节点的散列码以及它的位置。重新sorting节点的子节点应该明显改变生成的散列码。反映树的任何部分应明显改变生成的哈希码如果有帮助的话，我在我的项目中使用C＃4.0，虽然我主要是在寻找一个理论上的解决scheme，所以在另一个命令式语言中使用伪代码，描述或者代码就没有问题。 UPDATE 那么，这是我自己提出的解决scheme。这里得到了很多答案。每个节点（子树/叶节点）具有以下散列函数： public override int GetHashCode() { int hashCode = unchecked((this.Symbol.GetHashCode() * 31 + this.Value.GetHashCode())); for (int i = 0; i < this.Children.Count; i++) […]

什么是构buildFirebase数据的最佳方式？: 我是firebase的新手，我想知道什么是构build数据的最好方法。我有一个简单的例子：我的项目上有应用程序和应用程序。 1个申请人可以有几个申请。如何将这两个对象关联到firebase上？它是否像关系数据库一样工作？或者在数据devise方面需要完全不同的方法？

有没有人实际上实现了Fibonacci-Heap？: 有没有人实施过斐波纳契堆？我几年前就这样做了，但比使用基于arrays的BinHeaps慢了几个数量级。那时候，我认为这是一个很有价值的教训，就是研究并不总是像自称的那么好。然而，很多研究论文都是基于使用Fibonacci-Heapalgorithm的运算时间。你有没有设法产生一个有效的实施？还是你使用的数据集太大，斐波那契堆更有效率？如果是这样，一些细节将不胜感激。

自动完成的algorithm？: 我指的是当用户在Google中inputsearch词时，用于提供查询build议的algorithm。我主要感兴趣的是谷歌的algorithm能够显示：1.最重要的结果（最有可能的查询，而不是任何匹配）2.匹配子string3.模糊匹配我知道你可以使用Trie或者通用的trie来寻找匹配，但是它不能满足上面的要求。本文前面提到的类似问题

如何在哈希表和Trie（前缀树）之间进行select？: 所以如果我不得不在哈希表或前缀树之间进行select，那么导致我select哪一个的区别因素是什么。从我自己的天真的angular度来看，似乎使用一个特里特有一些额外的开销，因为它不存储为一个数组，但就运行时间而言（假设最长的键是最长的英文单词），它可以基本上是O （1）（相对于上限）。也许最长的英文单词是50个字符？一旦获得索引，哈希表就会立即查找。散列键获得索引，但似乎可以轻松地采取近50个步骤。有人能给我提供一个更有经验的观点吗？谢谢！

如何确定二叉树是否平衡？: 这些学年已经有一段时间了。在医院find了IT专家的工作。试图移动到现在做一些实际的编程。我现在正在研究二叉树，我想知道确定树是否高度平衡是最好的方法。我在想这个： public boolean isBalanced(Node root){ if(root==null){ return true; //tree is empty } else{ int lh = root.left.height(); int rh = root.right.height(); if(lh – rh > 1 || rh – lh > 1){ return false; } } return true; } 这是一个很好的实现？还是我错过了什么？