scheme - 查找调用许多过程的过程的增长顺序

Question

这段代码创建了一个平衡二叉搜索树，它是两个平衡二叉搜索树的交集。

(define (intersection-tree t1 t2)
    (list->tree (intersection-set (tree->list-2 t1) (tree->list-2 t2))))

• tree->list-2 将树展平为有序集。它需要 Theta(N)。
• intersection-settakes takes takes two sets and creates a new set with the intersection of the 两个输入集。它需要 Theta(N)。
• list->tree 将新创建的集合变成平衡的二叉搜索树。取 Theta(N)。

也就是说，我有一个过程调用 4 个采用 Theta(N) 的过程(列表-> 树、交叉集、两个树-> 列表)。我猜所有这些都需要 4N。忽略常数因子，它变成 Theta(N)。说相交树过程采用 Theta(N) 是否正确？

Answer 1

您的猜测是正确的，因为在您的函数中每个子任务仅执行一次，使用 Theta(N)，对于恒定次数，交集树过程使用 Theta(N)。