放牧代码和思想
专注自然语言处理、机器学习算法

多重对数函数The iterated logarithm function的定义

多重对数函数通俗地讲,就是使得lg(i) * n ≦ 1 的最小i值。在《算法导论》第三章有定义,对我来说是个新鲜玩意儿。

Functional iteration

We use the notation f(i)(n) to denote the function f(n) iteratively applied itimes toan initial

value of n. Formally, let f(n) be a function over the reals.For nonnegative integers i, we

recursively define

For example, if f(n) = 2n, then f(i)(n) = 2in.

The iterated logarithm function

We use the notation lg* n (read "log star of n") to denote the iteratedlogarithm, which is

defined as follows. Let lg(i) n be as defined above, with f(n) = lg n. Because the logarithm of a

nonpositive number is undefined, lg(i) n is defined only if lg(i-1)n > 0. Be sure to distinguish

lg(i) n (the logarithm function applieditimes insuccession, starting with argument n) from lgi

n (the logarithm of n raised to the ith power). The iteratedlogarithm function is defined as

lg* n= min {i= 0: lg(i) n 1}.

The iterated logarithm is a very slowly growing function:

lg* 2 = 1,

lg* 4 = 2,

lg* 16 = 3,

lg* 65536 = 4,

lg*(265536) = 5.

Since the number of atoms in the observable universe is estimated to beabout 1080, which is

much less than 265536, werarely encounter an input size n such that lg* n > 5.

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 多重对数函数The iterated logarithm function的定义

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机