分析线性表、二叉平衡树和哈希表存储数据时各自的优劣。

[问答题]

线性表顺序存储，查找O(n)

链式：优点：插入和删除不需要移动，空间有效利用缺点：大量访问操作时不如顺序存储结构。

顺序：优点：可随机存取表中任一元素。缺点：插入或删除操作时，需大量移动元素。

二叉平衡数存储，查找O(lgn), 插入O(lgn);

优点在平衡树中按序查找方便，缺点二叉平衡树的实现代价比较高。

哈希表存储，查找O(1),插入O(1)。缺点：不能显示序的信息，不能找出最大最小值。

二叉平衡树O(lgn)比哈希表O(1)不会大太多，若储存的数有序的要求，用二叉平衡树比哈希要好

发表于 2015-08-15 21:36:07 回复(0)

toraoh

线性表，插入的时间复杂度为O(1)，但是因内部无法保证有序，所以查找需要O(Length)的时间复杂度，而删除则取决于所用实现是链表还是数组，链表为O(1)，数组为O(Length)。虽然时间复杂度看起来比较糟糕，但是其时间常数相对后两者很小，比较适合于数据量极其小(<=100)、查询量也极其小的情况。

二叉平衡树，不论是插入、查询还是删除，均摊时间复杂度均近似为O(logn)，时间表现较稳定也较有效率，但是依赖于旋转操作来维持平衡（也有不需要旋转操作的二叉平衡树，但是工业上的主流实现选择还是红黑树，目前红黑树仍然被认为是时间效率最优的二叉平衡树，在随机数据下的确远优于Treap、Splay和AVL），每次操作需要的运算很多，常数很大，在数据量大且随机的情况下并不如hash。

Hash表，在完全随机的情况下，插入、查询和删除都可以认为是O(1)的时间复杂度（无冲突），有hash的常数存在但是好于二叉平衡树。但是hash在黑客恶意构造数据的情况下很可能会出现大量的冲突，导致hash表的查询等操作的时间复杂度成最坏情况O(n)，曾有被黑客用于恶意拒绝服务攻击的例子。而且hash表的内存消耗要比较大才能减少冲突，保证其性能表现。但是这仍然不妨碍hash表是目前工业界一种很流行的，在面对大量数据进行插入、查询、删除时选用的数据结构。

发表于 2015-08-15 16:14:33 回复(0)