文档章节

算法小论——第三章 又把新桃换旧符

难易
 难易
发布于 2015/02/21 01:12
字数 5336
阅读 2646
收藏 78

笔记

这一章主要是渐进记号和高中数学的回忆。

几个标记:

  1. Θ -- 上界和下界,绑定值,相当于f(n) ∈ [c1 * g(n), c2 * g(n)]
  2. Ω -- 闭区间下界,最好运行时间,相当于 f(n) ∈ [c * g(n), ∞)
  3. ω -- 开区间下界,最好运行时间,相当于 f(n) ∈ (c * g(n), ∞)
  4. Ο -- 闭区间上界,最差运行时间,相当于 f(n) ∈ [0, c * g(n)]
  5. ο -- 开区间上界,最差运行时间,相当于 f(n) ∈ [0, c * g(n))

其余部分,高中数学的内容都有,就不抄啦。

那么,数学对于算法导论的意义是什么?大家都怕数学,我也怕数学,觉得这个东西简直是摧残我智商方面的自信……不过呢,想要在理工科这个领域里面混,数学又是必须面对的。

陈皓(微博 @左耳朵耗子)有一篇博文,软件开发的“三重门”,里面讲程序员的3个阶段,业务功能、业务性能、业务智能,目前我还是停留在第1,2个阶段,如果我们想往第3个阶段前行,数学是个基本功。

当年我在学习物理的时候,老师在上课的时候教导我们,物理学家不需要像数学家那样严谨的学习推导数学,而是要把数学学活,创造性的用在物理领域。目标在于培养一种对于数学公式和自然现象相关性的直觉,由此洞察世界真相,变身高富帅,赢取白富美……就像杨振宁那样82还能娶28……哈哈哈,后面半句是我瞎编的。算法中的数学,也是这样吧。


习题答案

3.1-1

Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ-notation, prove that max(f(n), g(n)) = Θ(f(n) + g(n)).

一开始,我觉得这是显而易见的简单证明,结果看起来有点麻烦……

for n > n1, c1 * k(n) <= f(n) <= c2 * k(n), f(n) = Θ(k(n))
for n > n2, c3 * l(n) <= g(n) <= c4 * l(n), g(n) = Θ(l(n))

for n > max(n1, n2), max(f(n), g(n)) <= f(n) + g(n) <= c2 * k(n) + c4 * l(n)

到这里,证明max(f(n),g(n)) = O(f(n) + g(n))好像已经差不多了,但是对于证明Ω(下界)还不够。不过,也是可以变通的。

max(f(n),g(n) >= 1/2 * f(n) + 1/2 * g(n)

这个不等式的好处在于,在任何一点n上,如果

f(n) > g(n) 

max(f(n),g(n)) = f(n) = 1/2 * f(n) + 1/2 f(n) > 1/2 * f(n) + 1/2 * g(n)	

由于对称性,上面的不等式在g(n) > f(n)的时候也成立,于是,哈哈哈,Ω(下界)也证明了。

for n > max(n1, n2), max(f(n), g(n)) > 1/2(c1 * k(n) + c3 * l(n))

充分利用max的性质,是我解决这个小问题的关键……智商不足时间补啊……

3.1-2

Show that for any real constants a and b, where b > 0,

(n + a)^b = Θ(n^b)

额,这个证明么。。其实挺无聊的。。二项式展开,然后用最高次方才有用的性质来走。。就把问题平推了吧。。

哦,这里a和b是实数,不过我猜有理数和实数不影响这个结论,没办法,哈哈,作为物理学家,我们只有在有力气的时候才去追求数学上严谨性,能偷懒就偷懒了。

3.1-3

Explain why the statement, “The running time of algorithm A is at least O(n^2)” is meaningless.

这其实是一道GRE阅读理解题。

at least,意思就是最小,最少, >=

O(n^2), 意思就是<=,最大,最多

两者自相矛盾,所以是胡扯。这句话的意思堪比:

据我一位不愿意透露姓名的朋友唐马儒先生说,他是一个鉴黄师……

3.1-4

Is 2^(n+1) = O(2^n)? is 2^2n = O(2^n)?

前一个,2^(n+1) = 2 * 2^n = O(2^n),所以成立

后一个,n是变量,2^2n = 2^n * 2^n,所以不成立

3.1-5

Prove Theorem 3.1.

Theorem 3.1

For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

这个就是拿着定义凑一下的事儿,不干,嘿嘿。

3.1-7

Prove that o(g(n)) and ω(g(n)) is the empty set.

同上,不干。

3.1-8

We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n,m), we denote by O(g(n,m) the set of functions

O(g(n,m)) = { f(n,m) : 
there exist positive constants c, n0, and m0 
such that 
0 <= f(n,m) <= cg(n,m) 
for all n >= n0 or m >= m0 }

Give corresponding definitions for Ω(g(n,m)) and Θ(g(n, m)).

继续同上,没意思的活儿不干。也许在某些情况下需要双自变量的情况下用的上。

3.2-1

Show that if f(n) and g(n) are monotonically increasing functions, then so are the functions f(n) +(g(n) and f(g(n)) ,and if f(n) and g(n) are in addition nonnegative, then f(n)·g(n) is monotonically increasing.

高中数学题,或许是初中数学题?

3.2-2

Prove equation (3.16).

a^logb(c) = c^ logb(a)			3.16

go on

3.2-3

Prove equation (3.19). Also prove that n! = ω(2^n) and n! = o(n^n)

lg(n!) = Θ(nlgn)				3.19

这个式子对我来说有难度

lg(n!) < lg(n^n) = nlgn

上界好证,那么下界呢?

lg(n!) = lg(n*(n-1)...1) = lgn + lg(n-1) + lg(n-2) ... lg1

哦,提示里面说要用那个什么斯特林近似。

n! = √(2πn) (n/e)^n (1 + Θ(1/n))
lg(n!) = lg√(2πn) + nlg(n/e) + lg(1+Θ(1/n))
	   = (1/2)lg(2πn) + n(lgn - lge) + lg(1+c/n))
	   = Θ(lgn) + Θ(nlgn) + lg(n+c) - lgn
	   = Θ(nlgn)

好吧,靠着斯特林大神的庇佑,终于很容易的证明了这个式子,不过斯特林是怎么想到这个近似的呢?暂时不去想了……数学真神奇啊。

OK,继续证明另外两个式子.

n! = n(n-1)...2*1

当 n > 某个数字时,我猜

n(n-1)..2*1 > 2...2 (n个2)

因为双方的数目都是n个,对于前面n项左边都大于右边,只有最后一项1<2,所以,找一项对冲一下

(n-1)...2 > 2..2 (n-2个2)
n*1 > 2*2 (剩下2个2)

也就是说当 n > 4的时候上面两个不等式都成立,此时

n! > 2^n
n! = ω(2^n)

OK,继续证明最后一个式子

n! < n^n
n(n-1)...2*1 < n...n
n! = o(n^n)

两边都是n个,左边小于右边,得证。

3.2-4 *

Is the function 「lgn]! polynomially bounded? Is the function 「lg lgn]! polynomially bounded?

对于第一个问题,我先试探一下,假设

n = 32, lgn = 5, 5! = 120
n = 16, lgn = 4, 4! = 30
n = 8,  lgn = 3, 3! = 6

这里n以2^k的速度变大时,「lgn]!以k!的速度变大,那么哪一个变得更快?这两者之间的差值是多少?

由上面那个习题3.2-3可以知道,k! = ω(2^k),k!增长的更快,这也从我上面的试探中可以看出来,同时,k!比2^k大了不止一个多项式的差距,所以我大胆猜测,「lgn]!不是多项式增长的。具体的证明留给数学家,wahaha。

那么问题更推一步 「lg lgn]!呢,就是2^2^k和k!之间的比较。

k = 1, 2^2^k = 4,   k! = 1
k = 2, 2^2^k = 16,  k! = 2
k = 3, 2^2^k = 256, k! = 6
k = 4, 2^2^k = 65536, k! = 24

也就是说,2 ^2 ^k的增长速度远远大于k!的增长速度,反过来说,对「lg lgn]! 而言,n以线性增加时,「lg lgn]! 在数轴上会小于n,最后趋向于0,所以我猜测

「lg lgn]! = Θ(1)

3.2-5 *

Which is asymptotically larger: lg(lg * n) or lg * (lgn) ?

其实,我不懂这个*号到底是谁神马意思?先空着。哦,回头去看课本,这个高中没教过。

n = 16

lg * n = 3
lg(lg * n) = lg3

lg * (lg 16) = lg * 4
			 = 2

lg 3 < 2, 所以看起来后面那个大一点,换个数字

n = 65536

lg * n = 4
lg(lg * n) = 2

lg * (lg 65536) = lg * (16)
				= 3

好了,经过两次的猜测,基本就能看出来后面那个大了。

3.2-6

Show that the golden ratio φ and its conjugate φ' both satisfy the equation

x^2 = x + 1

黄金分割比的定义吧,二次方程的解法,初中数学跳过。

3.2-7

Prove by induction that the ith Fibonacci number satisfies the equality

F[i] = (φ^i -  φ'^i) / √5

where φ is the golden ratio and φ' is its conjugate.

好吧,继续归纳法,显然

F[0] = 0
F[1] = 1

假设

F[i-1] = (φ^(i-1) - φ'^(i-1)) / √5
F[i-2] = (φ^(i-2) - φ'^(i-2)) / √5

F[i] = F[i-1] + F[i-2]
	 = (φ^(i-1) + φ^(i-2) - φ'^(i-1) - φ'^(i-2)) / √5
	 = (φ^(i-2)(φ + 1) - φ'^(i-2)(φ' + 1)) / √5

凑一下

φ + 1 = (3 + √5) / 2
φ^2   = (1 + 2√5 + 5) / 4 = (3 + √5) / 2
φ + 1 = φ^2

φ'+ 1 = φ'^2 //同理

代入后,得到

F[i] = (φ^i -  φ'^i) / √5

得证。

关于斐波那契数列,在TED上有一个精彩的演讲,抨击教育制度的,不妨一看

神奇的斐波那契数列

我一直没搞明白为什么这个数列和黄金分割有关,至少没看出深刻的联系,由公式能看出不少东西,但还是缺乏直观的理解。

3.2-8

Show that klnk = Θ(n) implies k = Θ(n/lnn).

klnk = Θ(n) = n
n / lnn = klnk /(ln(klnk))
		= klnk / (lnk + lnlnk)
		< klnk / lnk (当k足够大之后,lnlnk > 0的情况下)

这样,大致就可以看出k的渐进时间了,当然是很粗糙的证明,中间还有常数不等式都没考虑。这个题目的意义在于,对于渐进时间,不但有函数的上界、下界、传导性、交换律、对称性这些特性,还有反函数的特性,在某些领域可能用的上。


问题答案

3-1 Asymptotic behavior of polynomials

Let

p(n) = ∑a[i]n^i (i = 0 to d)

where a[d] > 0, be a degree-dpolynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. if k >= d, then p(n) = O(n^k).
b. if k <= d, then p(n) = Ω(n^k).
c. if k  = d, then p(n) = Θ(n^k).
d. if k  > d, then p(n) = ο(n^k).
f. if k  < d, then p(n) = ω(n^k).

哈哈哈无聊的问题我就不证了吧

3-2 Relative asymptotic growths

Indicate, for each pair of expressions(A, B) in the table below, whether A is O, o, Ω, ω or Θ of B. Assume that k >= 1, ∈ > 0, and c > 1 are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

	A			B			O	o	Ω	ω	Θ
a.	(lgn)^k		n^∈			√	√	×	×	×
b.	n^k			c^n			√	√	×	×	×
c.	√n			n^(sin n)	×	×	√	√	×
d.	2^n			2^(n/2)		×	×	√	√	×
e.	n^(lgc)		c^(lgn)		×	×	×	×	√
f.	lg(n!)		lg(n^n)		×	×	×	×	√

a. 如果k=2,∈=1,我测算了一下是(lgn)^2=o(n),回头继续看课本(课本就是用来回头的哈哈哈),书上有这样的式子:

(lgn)^b = o(n^a)

b.同样的

n^b = o(a^n)

c.sin n <= 1, >= -1, 而 √n 可以一直增长,所以 √n 是赢家。

d. 2^n = 2^(n/2) * 2^(n/2),2^n要大很多,比较牛逼。

e. 这两个式子其实是一样的!只是伪造不在场证明而已!真相只有一个!哈哈哈……

f. 这其实也是个改头换面,lg(n^n) = nlgn

lg(n!) = Θ(nlgn)				3.19

所以两者还是一样地,就是拐了个弯的一样。

这题其实有助于帮我们建立一些直觉,例如指数函数比幂函数快,对数的n次方还是没有幂函数快,等等

3-3 Ordering by asymptotic growth rates

a. Rank the following functions by order of growth; that is, find an arrangement g1, g2,...,g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), ..., g29 = Ω(g30). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).

lg(lg*n)	2^(lg*n)	(√2)^(lgn)	n^2			n!		(lgn)!
(3/2)^n		n^3			(lgn)^2		lg(n!)		2^2^n	n^(1/lgn)
lnlnn		lg*n		n*2^n		n^lglgn		lnn		1
2^lgn		(lgn)^lgn	e^n			4^lgn		(n+1)!	(√lgn)
lg*(lgn)	2^(√2lgn)	n			2^n			nlgn	2^(2^(n+1))

这里继续是苦力活啊……抄了半天题目,好像对齐还成问题? 不多说,这种题目的解决方案是先立标杆,分类,从高阶到低阶的直接分类为:

指数之指数	2^2^n,2^(2^(n+1))
阶乘		n!,(n+1)!
指数函数	(3/2)^n,2^n,e^n
幂函数		n,n^2,n^3
对数函数	lnn,(lgn)^2
多重对数	lg(lg*n),lg*(lgn) == lg*n
常数		1

注,根据定义,多重对数少取一次的意思在于

lg*(lgn) = (lg*n) - 1
=>
lg*(lgn) = Θ(lg*n) //这些符号太啰嗦,后面我就用等号大于号小于号之类了的:-)

接下来的工作就是把剩下的这些插进去,看位于哪里合适,一个一个看


####1. 2^(lg*n)

2^(lg*n) < 2^(lgn) = n^(lg2) = n

那么这个比幂函数小,那么是否比对数函数也小呢?

n = 16
lg * n = 3
2^3 = 8
lg n = lg16 = 4

所以,合理的推测是,比一般的多重对数大,但是小于对数函数

对数函数	lnn,(lgn)^2
----		2^(lg*n)
多重对数	lg(lg*n),lg*(lgn),lg*n

####2. (√2)^(lgn)

(√2)^(lgn) = n ^ lg(√2) = n ^ (1/2) = √n

插入幂函数最小的档次

幂函数		(√2)^(lgn),n,n^2,n^3

####3. (lgn)!

(lgn)! < n!

n = 16
(lgn)! = 4! = 24
2^16 >> 24
(lgn)! < 2^n
16^2 = 256 >>24
(lgn)! < n^2

n = 32
(lgn)! = 5! = 120
n^2 = 1024
而显然
(lgn)! > (lgn)^2

插入对数函数的最后

对数函数	lnn,(lgn)^2,(lgn)!

####4. lg(n!)

lg(n!)

根据习题3.2-3

lg(n!) = nlgn

位于幂函数中间

幂函数		(√2)^(lgn),n,nlgn == lg(n!),n^2,n^3

####太长了重新抄一遍

指数之指数	2^2^n,2^(2^(n+1))
阶乘		n!,(n+1)!
指数函数	(3/2)^n,2^n,e^n
幂函数		(√2)^(lgn) == √n 见【2】,n,nlgn == lg(n!) 见【4】,n^2,n^3
对数函数	lnn,(lgn)^2,(lgn)! 见【3】
----		2^(lg*n) 见【1】
多重对数	lg(lg*n),lg*(lgn) == lg*n
常数		1

剩下需要插入的有

n^(1/lgn), lnlnn, n*2^n, n^lglgn, 2^lgn, 
(lgn)^lgn, 4^lgn, (√lgn), 2^(√2lgn)

####5. n^(1/lgn)

继续

常数		1 < n^(1/2) (当 n > 4时)
n = 16
n^(1/lgn) = 16^(1/4) = 2
lg16 = 4
n^(1/lgn) < lgn
n = 64
n^(1/lgn) = 64^(1/6) = 2

猜测

n^(1/lgn) = 2
n^(1/lgn) = n^(logn 2) = 2

所以

常数		1, n^(1/lgn) == 2

####6. lnlnn

lnlnn < lnn
但猜测 lnlnn > 2^(lg*n)
对数函数	lnn,(lgn)^2,(lgn)!
----		lnlnn
----		2^(lg*n)

####7. n*2^n

n*2^n > 2^n
e^n = (2.71)^n = 2^n * (1.x)^n > 2^n * n

插入

指数函数	(3/2)^n,2^n,n*2^n,e^n

####8. n^lglgn

n^lglgn < n^(lgn)
n^lglgn > n^3 (当n足够大)
那么和2^n比较呢?

n = 8
n^(lglgn) = 8^lg3 = (2^3)lg3 = (2^lg3)^3 = 3^3 = 81
2^8 = 256

猜测

指数函数	(3/2)^n,2^n,e^n
----		n^lglgn
幂函数		(√2)^(lgn) == √n,n,nlgn == lg(n!),n^2,n^3

####9. 2^lgn, 4^lgn 2^lgn = n 4^lgn = n^2 幂函数 (√2)^(lgn) == √n,2^lgn == n,nlgn == lg(n!),n^2 == 4^lgn,n^3


####10. (lgn)^lgn

(lgn)^lgn = n^(lglgn)

####11. (√lgn)

(√lgn) < lnn
对数函数	(√lgn),lnn,(lgn)^2,(lgn)!

####12. 2^(√(2lgn))

2^(√(2lgn)) = (2^lgn)^(√(2/lgn)) = n^(√(2/lgn))
当n变大时,指数其实无限趋向于0,总之比0.5要小,所以排名在幂函数里面最小
幂函数		2^(√2lgn),(√2)^(lgn) == √n,n,nlgn == lg(n!),n^2,n^3

所以,最后的总排名是!

指数之指数
2^(2^(n+1))
2^2^n

阶乘
(n+1)!
n!

指数函数
e^n
n*2^n 					见【7】
2^n
(3/2)^n

--无名函数--
n^lglgn == (lgn)^lgn 	见【8】 见【10】

幂函数
n^3
n^2 == 4^lgn 			见【9】
nlgn == lg(n!) 			见【4】
2^lgn == n 				见【9】
(√2)^(lgn) == √n 		见【2】
2^(√2lgn) 				见【12】

对数函数
(lgn)!					见【3】【错,详见后】
(lgn)^2
lnn
(√lgn) 					见【11】

--无名函数--
lnlnn					见【6】
2^(lg*n)				见【1】

多重对数
lg*(lgn) == lg*n
lg(lg*n)

常数
n^(1/lgn) == 2			见【5】
1

累死,一个晚上就这么一题搞完了,回头再去对答案~~


经过对答案后,我发现有个小小的问题,就是对于

(lgn)!

我判断错了,答案中的说法是

(lgn)! > n^3

理由是对双方一起取对数

lg(x!) = xlgx (习题3.2-3)
lg((lgn)!) = lgn * lg(lgn)

然后试着对n^3取对数

lg(n^3) = 3lgn

于是,这下就是

lgn * lglg(n)  vs  3lgn

可以看出双方都有lgn的因子,但是lglg(n) >> 3,于是左方胜利!可以说,这是出乎我的意料的,我前面通过手工穷举法做了错误的判断,在这里用精妙的数学做了无懈可击的推到 -_- ,那么,我能从中学到什么呢?在真实的情况下我能依赖于手工的穷举吗?对于一个数学笨蛋来说,只有2种方法可以搞定

  1. 用计算机模拟,把这2个函数真的画图搞出来
  2. 找个数学专家,把我不确定的地方和他聊,请他帮我解决

b. Give an example of a single nonnegative function f(n) such that for all functions gi(n) in part (a), f(n) is neither O(g(n)) nor Ω(g(n)).

上面的这些函数基本上填满了数轴,如果要找出一个函数既不是O也不是Ω,就需要找一个震荡的很厉害的函数,例如

2^(2^(2^n)) * | sin n |

首先这个函数在最大的时候比指数之指数还要大,但是最小的时候可以是0。

3-4 Asymptotic notation properties

Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

a. f(n) = O(g(n)) implies g(n) = O(f(n)).

错,f(n) <= g(n) 不代表 g(n) <= f(n)

b. f(n) + g(n) = Θ(min(f(n),g(n)))

粗一看这题好像和3.1-1差不多,但max和min的性质不一样,我套了一下max的证明发现不成立。反过来想,假设

g(n) = n^2, f(n) = n
则
f(n) + g(n) = n^2 + n = Θ(n^2)
min(f(n), g(n)) = n = Θ(n)

于是,不成立

c. f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) >= 1 and f(n) >= 1 for all sufficiently large n.

成立,因为lg是个单调递增函数,a

f(n) <= g(n) (当n大于某一常数时)
则
lg(f(n)) <= f(g(n))
f(n) > 1保证了lg(f(n)) > 0 ,满足了本章所有函数都非负的初始条件。

d. f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n)).

同上也成立,由于指数函数都是正的,所以不需要额外的条件

e. f(n) = O((f(n))^2).

不成立,如果f(n) < 1,约平方越小,所以不能这么写。

f. f(n) = O(g(n)) implies g(n) = Ω(g(n))

按照定义成立

g. f(n) = Θ(f(n/2))

不成立,f(n/2)就是把f(n)在x轴上横向拉长一倍,对于多项式函数来说是成立的,n/2不影响最高次方的数,但对于指数函数例如2^n这样的,就不行。

f(n) = 2^n
f(n/2) = 2^(n/2)

显然f(n/2)和f(n)不在同一个班次上啊

h. f(n) + o(f(n)) = Θ(f(n))

成立,

f(n) + o(f(n)) >= f(n)
f(n) + o(f(n)) <= 2f(n)

得证

3-5 Variations on O and Ω

Some authors define in a slightly different way than we do; let’s use Ω∞ (read “omega infinity”) for this alternative definition. We say that f(n) = Ω∞( g(n) ) if there exists a positive constant c such that f(n) > cg(n) for infinitely many integers n.

**a. Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or f(n) == Ω∞( g(n) ) or both, where as this is not true if we use Ω in place of Ω∞ **

首先O和Ω是互相排斥的,不可能both。其次这个Ω∞有啥好处能够兼容呢?对于both这种情况我很难想象

存在c1, f(n) <= c1 g(n), n > n0
存在c2, f(n) > c2 g(n), n 有无穷个

b. Describe the potential advantages and disadvantages of using Ω∞ instead of Ω∞ to characterize the running times of programs.

目前还没看出有无穷个n的好处,因为无穷个不等于所有大于n0的,这样不能保证f(n)的性质,例如 sin(n) + 1 = Ω∞(1), 因为sin(n)在1和-1间波动,这题看不出妙处,先跳过。

Some authors also define O in a slightly different manner; let’s use O’ for the alternative definition. We say that f(n) = O’(g(n)) if and only if |f(n)| = O(g(n))

c. What happens to each direction of the “if and only if” in Theorem 3.1 if we substitute O’ for O but still use Ω ?

Theorem 3.1
For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) =  O(g(n)) and f(n) =  Ω(g(n)).

这题我就更加看不懂了,出来了绝对值,而本章讨论的都是大于0的函数。。。继续跳过

d问题不抄也罢,另一个脱离前提的设定

3-6 Iterated functions

We can apply the iteration operator * used in the lg * function to any monotonically increasing function f(n) over the reals. For a given constant c ∈ R, we define the iterated function f.c. by*

f.c.*(n) =  min{ i >=0,   f(i)(n) <= c }

which need not be well defined in all cases. In other words, the quantity f.c. 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 functions f(n) and constants c, give as tight a bound as possible on f.c.

首先题目中的f.c.*(n)也是一个n的函数,所以需要一个tight bound来表示

   f(n)    |    c     |   f.c.*(n)
a. n - 1   |    0     |   n

a是显然的

b. lgn     |    1     |   lg * n  

b就有点困难了,你用什么函数来表示需要递归lg几次到1呢?这个无法直接表达,只能用书里面的lg * n

c. n/2     |    1     |   lgn

c还是比较明确的,需要除几次2, 也就是2的几次方能到n,验证下n = 2, i = 1,符合搞定

d. n/2     |    2     |   lgn - 1

少除一次,继续通过验证得出

e.√n       |    2     |

这个不会,开方开几次小于2?好像没什么规律,后面的也无法做出来,就放一放吧……

© 著作权归作者所有

难易

难易

粉丝 272
博文 45
码字总数 103644
作品 2
杭州
程序员
私信 提问
加载中

评论(5)

兵戈天下
兵戈天下

引用来自“foy”的评论

威武霸气
霸气侧漏啊
foy
foy
威武霸气
d
danann
很好
levinelee
levinelee
数学,,
itfanr
itfanr
算法 是高效的灵魂
GitHub上README写法暨markdown语法解读

自从开始玩GitHub以来,就 越来越 感觉它有爱。最近对它的 README.md 文件颇为感兴趣。便写下这贴,帮助更多的还不会编写README文件的同学们。 README文件后缀名为md。md是markdown的缩写,m...

中成才
2014/12/10
377
0
分享两本约会把妹的技巧,把妹达人电子书

李珂珂,国家级知名PUA绅士兼PUA导师,郑州风信文化传播有限公司签约专职情感导师,帮助数以千计的单身男人脱离感情困扰,找寻美好的恋情。80后最小的专业情感分析导师,天涯百万人气情感专家...

mindlook
2018/03/28
0
0
机器学习的最佳学习路线原来只有四步

AI这个词相信大家都非常熟悉,近几年来人工智能圈子格外热闹,光是AlphoGo就让大家对它刮目相看。今天小天就来跟大家唠一唠如何进军人工智能的第一步——机器学习。 在机器学习领域,Python已...

ufv59to8
2018/05/12
0
0
GitHub上README写法暨GFM语法解读,gitoschina也适用

自从开始玩GitHub以来,就越来越感觉它有爱。最近对它的README.md文件颇为感兴趣。便写下这贴,帮助更多的还不会编写README文件的同学们。 README文件后缀名为md。md是markdown的缩写,markd...

memristor
2014/06/23
996
0
GitHub上README.md教程

最近对它的README.md文件颇为感兴趣。便写下这贴,帮助更多的还不会编写README文件的同学们。 README文件后缀名为md。md是markdown的缩写,markdown是一种编辑博客的语言。用惯了可视化的博客...

xxjbs001
2015/03/11
246
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
今天
7
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
今天
6
0
Flutter系列之在 macOS 上安装和配置 Flutter 开发环境

本文为Flutter开发环境在macOS下安装全过程: 一、系统配置要求 想要安装并运行 Flutter,你的开发环境需要最低满足以下要求: 操作系统:macOS(64位) 磁盘空间:700 MB(不包含 IDE 或其余...

過愙
今天
6
0
OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
2.5K
16
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
42
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部