AVL树中序遍历实现并集的最坏时间复杂度分析

题目给出的实现代码 #

并集入口函数 #

AVLTree TreeUnion(t1, t2){
    newTree = AVLTreeNew();
    traverse(t1->root, newTree);
    traverse(t2->root, newTree);
    return(newTree);
}

遍历插入函数 #

// 注：原始代码存在书写笔误
void traverse(AVLTree t1, AVLTree newTree){
    if(t == NULL){ // 参数名与内部使用变量不匹配
        return;
    }
    traverse(t->left);
    AVLInsert(newTree, t->item);
    traverse(t->left); // 标准中序遍历此处应为t->right，否则会重复遍历左子树导致栈溢出
}

原复杂度推导的错误 #

你得出O(x+y)结论的核心问题是对插入开销求和的渐近阶判断错误，具体问题如下：

• 你列出的插入开销序列O(log1) + O(log2) + ... + O(log(x+y))，求和结果不是线性阶。根据对数运算性质，这个和等于log((x+y)!)，结合斯特林公式可以证明，log(n!)的渐近复杂度是O(n log n)，n取x+y时对应复杂度为O((x+y)log(x+y))。
• 首个元素插入时开销是O(1)还是O(log1)不影响最终结论，二者都属于常数级开销，不会改变整体渐近复杂度。
• 遍历两棵原树的开销确实是O(x+y)，但这个阶低于插入操作的总开销，最终会被高阶项覆盖。
• 额外注意：给出的traverse函数存在明显笔误，两次递归访问左子树、未访问右子树，还存在参数名不匹配的问题，实际运行会触发栈溢出，修正为标准中序遍历（左子树-根节点-右子树）后，遍历部分的开销才是O(x+y)。

正确的复杂度分析思路 #

分析这类递归实现的算法复杂度，可以按两步走：

• 第一步：拆分所有独立操作，分别计算每类操作的总开销
  • 遍历操作：修正后的中序遍历每个节点仅访问1次，不管树的结构如何，遍历x个节点的树固定需要O(x)时间，遍历y个节点的树固定需要O(y)时间，这部分总开销为O(x+y)。
  • 插入操作：AVL树是平衡二叉搜索树，单次插入（含平衡旋转调整）的最坏时间复杂度和当前树高正相关，为O(log k)，k是插入操作执行时新树的已有节点数。最坏场景下两棵树没有重复元素，总共需要执行x+y次插入，总插入开销求和后为O((x+y)log(x+y))。
• 第二步：取所有操作中的最高阶作为整体算法的最坏复杂度
  由于O((x+y)log(x+y))的增长速度远快于O(x+y)，因此这个算法的最坏时间复杂度是O((x + y) log(x + y))，不是线性阶。

内容的提问来源于stack exchange，提问作者Kerelos Tawfik