algorithm - MERGE SORT 的 DIVIDE 步骤的基本混淆

Question

在Merge Sort中，每个元素的Divide步骤的运行时间被认为是theta(1)，即CLRS中的常数时间。

---

我的困惑是:Let divide 是一个基本运算，需要常数时间 C1。现在，考虑伪代码

现在，当第一次调用MERGE-SORT 函数时，它需要C1 来划分输入(注意:- 我们没有考虑时间由 Merge 函数采用)而这个MERGE-SORT 将把输入lg(n) 时间( 或者我们可以说它会称自己为lg((n))次)所以划分输入的总时间应该是C1 * lg(n)即 theta(lg(n))。

---

但在 CLRS 中:

如果我们考虑到 Divide Step 将需要 theta(1) 时间(作为整体)

注意:lg是以2为底的log

附言- 提前抱歉，因为我的英语没有达到那个标准。欢迎编辑:)

Answer 1

除法的一步确实需要常数时间 O(1)。

但是和你想的相反，一共有Θ(N)个除法(1+2+4+8+...N/2)。

无论如何，这没有被考虑在内，因为总的合并工作量是 Θ(N Log N)。