binary-search-tree - 平衡二叉搜索树的摊销复杂度

Question

我不完全确定摊销复杂性意味着什么。采用平衡二叉搜索树数据结构（例如红黑树）。正常搜索的成本自然是 log(N)，其中 N 是节点数。但是按升序排列的 m 次搜索序列的摊销复杂度是多少。它只是log（N）/m吗？

Answer 1

好吧，您可以将渐近分析视为设置算法运行时间上限的严格方法，其中摊销分析是一种自由方法。

例如，考虑具有两个语句 S1 和 S2 的算法 A。执行 S1 的成本是 10，S2 是 100。这两个语句都放在一个循环中，如下所示。

n=0;
while(n<100)
{
  if(n % 10 != 0)
  {
    S1;
  }
  else
  {
    s2;
  }
  n++;
} 

这里 S1 执行的次数是 S2 的 10 倍。但是渐近分析只会考虑 S2 需要 10 个单位的时间并且它在一个循环中执行 100 次的事实。因此，执行时间的上限约为 10 * 100 = 1000。其中，摊销分析平均了语句 S1 和 S2 的执行次数。因此，执行的上限时间约为 200 次。因此，摊销分析可以更好地估计执行算法的上限。

Answer 2

我认为是 mlog(N) 因为你必须做 m 个搜索操作（每次从根节点到目标节点），而单个操作的复杂度是 log(N)。

编辑：@user1377000 你是对的，我把分期复杂度和渐近复杂度弄错了。但我不认为它是 log(N)/m... 因为不能保证您可以在 O(logN) 时间内完成所有 m 搜索操作。

什么是算法的摊销分析？ 我认为这可能会有所帮助。

Answer 3

在平衡搜索树的情况下，摊销复杂度等于渐近复杂度。每个搜索操作都需要O(logn)时间，包括渐近的和平均的。因此，对于m搜索，平均复杂度为O(mlogn)。

Answer 4

一次性输入要找到的物品。

您可以从分而治之的角度来考虑它。

1. 取x根节点中的项目。
2. 二进制搜索x到您的项目数组m。
3. 将数组划分为小于x和大于的事物x。（忽略等于 的东西x，因为你已经找到了。）
4. 递归地在你的左孩子中搜索前一个分区，在你的右孩子中搜索后者。

一个最坏的情况：您的项目数组只是叶节点中的事物列表。（n大致是2m。）您必须访问每个节点。您的搜索将花费lg(n) + 2*lg(n/2) + 4*lg(n/4) + ...。那是线性的。可以将其视为进行越来越小的二进制搜索，直到您将数组中的每个元素都命中一次或两次。

我认为还有一种方法可以通过在搜索后跟踪您在树中的位置来做到这一点。C++std::map和std::set返回迭代器可以在树中左右移动，它们可能具有可以利用现有迭代器进入树的方法。