Re: [其他] 問一題離散
※ 引述《PowerKid (暴力小孩)》之銘言：
: For a given constant c 屬於 R,we define the iterated function f by
: f(n) = min{i>= 0 :f(i)(n)<=c} (i是在f的上面)
: In other words, the quantity f (n) is the number of iterated applications of the function f required to reduce its
: argument down to c or less.
: For each of the following function f(n) and constant c, give as tight a bound
: as possible on f*c (n).
: f(n) c
: 1. n^1/2 1
: 2. n^(1/3) 2
: 3. n/lgn 2
: 第一題 n^(1/2^i)<=1
: 取LOG (1/2^i)logn<=log 1 =0
: 然後我找不出i 就不會做了
: 第三題完全不會
: 第二題 跟第一題同樣方法 可是i的值找不到
你應該想想 是否存在 i 使得 f(i)(n) <= c
對於 1, 如果 n <= 1, 則 i=0, 但 n > 1 時， f(i)(n) > 1 for all i >=0
3 可能複雜些，但應該和 1 類似
至於 2 , (1/3)^i logn <= log2
(1/3)^i <= log2 / logn
-ilog3 <= loglog2 - loglogn
i >= (loglogn - loglog2)/log3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.129.98
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：