1

因此，我试图了解 BST 和散列的某些函数的数据类型和大 O 表示法。

那么首先，BST 和散列是如何存储的？BST 通常是数组，还是链表，因为它们必须指向它们的左叶和右叶？哈希呢？在基于计算的搜索方面，我很难找到有关散列的明确信息。我知道散列最好用一系列链来实现。这是为了更快的搜索还是减少创建分配数据类型的开销？

下面这个问题对我来说可能只是不好的解释，但是是什么让遍历函数与 BST、散列和 STL 容器中的搜索函数不同？BSTS 的遍历大 O(N) 是因为您实际上是在访问每个节点/数据成员，而 search() 可以通过消除一半的搜索字段来减少其时间？

并且有点相关，为什么在 STL 中，list.insert() 和 list.erase() 有一个大 O(1) 而向量和双端队列对应物是 O(N)？

最后，为什么 vector.push_back() 会是 O(N)？我认为该函数可以按照 O(1) 的方式来完成，但我遇到过文本说它是 O(N)：

vector<int> vic(2,3);
vector<int>::const iterator IT = vic.end();

//wanna insert 4 to the end using push_back

IT++;
(*IT) = 4;

希望这有效。我有点累，但我很想解释为什么类似的事情不会有效或不合理。谢谢

4

2 回答 2

1

BST（有序二叉树）是一系列节点，其中一个父节点指向它的两个子节点，而这两个子节点又指向它们的最大两个子节点，等等。它们在 O(n) 时间内被遍历，因为遍历会访问每个节点。查找需要 O(log n) 时间。插入需要 O(1) 时间，因为在内部它们不需要一堆现有节点；只需分配一些内存并重新瞄准指针。:)

散列 (unordered_map) 使用散列算法将元素分配给存储桶。通常桶包含一个链表，因此哈希冲突只会导致同一个桶中的多个元素。正如预期的那样，遍历将再次是 O(n)。查找和插入将摊销 O(1)。摊销意味着平均为 O(1)，尽管单个插入可能会导致重新散列（重新分配存储桶以最大程度地减少冲突）。但随着时间的推移，平均复杂度为 O(1)。但是请注意，大 O 表示法并没有真正处理“常数”方面。唯一的增长顺序。散列算法中的恒定开销可能足够高，以至于对于某些数据集，O(log n) 二叉树的性能优于散列。尽管如此，散列的优点是它的操作是恒定的时间复杂度。

搜索函数利用“顺序”的概念（在二叉树的情况下）；通过 BST 的搜索与在有序数组上的基本二分搜索具有相同的特征。O(log n) 增长。哈希并不真正“搜索”。他们计算桶，然后快速通过碰撞找到目标。这就是为什么查找是恒定时间的原因。

至于插入和擦除；在基于数组的序列容器中，目标之后的所有元素都必须向右移动。C++11 中的移动语义可以提高性能，但操作仍然是 O(n)。对于链接的序列容器（list、forward_list、trees），插入和擦除只是意味着在内部摆弄一些指针。这是一个恒定时间的过程。

push_back() 将是 O(1)，直到您超过向量的现有分配容量。一旦超过容量，就会进行新的分配以生成一个足够大以容纳更多元素的容器。然后需要将所有元素移动到更大的内存区域，这是一个 O(n) 过程。我相信 Move Semantics 在这里也可以提供帮助，但它仍然是 O(n)。向量和字符串的实现方式是，当它们为不断增长的数据集分配空间时，它们分配的空间超过了它们需要的空间，以期待额外的增长。这是一种效率保障；这意味着典型的 push_back() 不会触发新的分配并将整个数据集移动到更大的容器中。但最终在足够的 push_backs 之后，就会达到极限，并且向量'

于 2012-12-11T09:29:54.300 回答
0

遍历是指访问每个节点，而搜索只是找到一个特定的节点，所以你的直觉就在那里。O(N) 复杂度，因为您需要访问 N 个节点。

std::vector::insert用于在中间插入，它涉及将所有后续元素复制一个插槽，以便为插入的元素腾出空间，因此 O(N)。链表没有这个问题，因此 O(1)。类似的逻辑erase。deque属性类似于vector

std::vector::push_back 是一个 O(1) 操作，在大多数情况下，只有在超出容量并且需要重新分配 + 复制时才会偏离。

于 2012-12-11T08:58:19.033 回答