该算法的变量值和时间复杂度

Question

问题：

1. 算法执行结束时的 p 和 q 值
2. 该算法的时间复杂度

我的回答：

Answer 1

第一个内部循环将

p

递增一定次数，等于

n

的以 2 为底的对数。当外层循环执行

n

次时，

p

的最终值为

n.lg(n)

。

现在，第二个循环将

q

递增等于

lg(p)

的次数，其中

p

取值

k.lg(n)

，或

1, 2, 3, ... n

乘以

lg(n)

。

q

的最终值为

lg(n!)+lg(lg(n))

。

时间复杂度很容易计算，因为操作数量与

p

的增量数量加上

q

的增量加上一些可忽略不计的开销成正比。最后，

Θ(lg(n!)) = Θ(n.lg(n))

。

---

请注意，这些只是近似值，因为真正的迭代次数是对数的下限，而不是对数。