算法导论 3-6 多重函数

2021-08-21 本文已影响0人风海铜锣君

题目

（多重函数）我们可以把用于函数 lg* 中的重复操作符 * 应用于实数集上的任意单调递增函数 f(n) 。对给定的常量 c∈R ，我们定义多重函数 f*c 为：

f*c(n) = min { i >= 0: f^(i)(n) <= c }

该函数不必在所有情况下都为良定义的。换句话说，值 f*c(n) 是为缩小其参数到c或更小所需要函数f重复应用的数目。

对如下每个函数 f(n) 和常量 c ，给出 f*c(n) 的一个尽量紧确的界。