2020-08-27 算法导论 第三章 多重函数

看到算法导论这里不太明白,查了查网,赶紧记录。

多重函数

算法导论中使用f^{(i)}(n)来表示函数f(n)重复i次作用于一个初值n上。形式化的假设f(n)为实数集上的一个函数。对非负整数i,我们递归地定义
f^{(i)}(n)=\begin{cases} n&若i=0\\ f(f^{(i-1)}(n))&若i>0 \end{cases}
例如,若f^{(i)}(n)=2^in

多重对数函数

定义多重对数函数为:
lg^*n=min\{i\ge 0:lg^{(i)}n\le 1\}
这是啥意思呢?是这样的首先这个多重对数函数输入的n输出的是i。也就是使结果小于等于0的i也就是多重函数的重数。

如:

lg^*2结果是1,因为只需执行一次就可以使结果小于等于1

lg^*4结果是2,因为lg4=2结果大于1,再次执行lg2=1,所以i=2,即输出的结果

类似的lg^*16=3,lg^*65536=4,lg^*(2^65536)=5,这个输入已经非常巨大了比整个宇宙可探测到的原子数目还多,所以我们很少遇到一个让多重对数函数值大于5的输入规模n。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。