交大110 資料結構與演算法第29題｜資料結構 Ch1 演算法基礎

資料結構›Ch1 演算法基礎

第 33 題／共 57 題

33. Function Iteration、Iterated Logarithm

#DS-01-033易Function IterationIterated Logarithm

Function iteration: The notation $f^{(i)}(n)$ (NOT $f^i(n)$ ) denotes the function $f(n)$ iteratively applied i times to an initial value of n. For non-negative integers i, $f^{(i)}(n)=n$ if $i=0$ , and $f^{(i)}(n)=f(f^{(i-1)}(n))$ if $i>0$ . Now let $\lg n$ represent base-2 logarithm. $\lg^{(i)} n$ is defined as above with $f(n)=\lg n$ ; note that $\lg^{(i)} n$ is defined only if $\lg^{(i-1)} n>0$ . Let $\lg^* n$ denote the iterated logarithm, given by $\lg^* n=\min\{i\ge 0: \lg^{(i)} n\le 1\}$ . Which of the following statement(s) is(are) correct?

📄 交大110

▤完整推導請見《WH 資工筆記 · 資料結構》Ch1 演算法基礎

本章題號 · 21–40 / 57