本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 近似
- 增长的数量级
- 对数函数的运算法则
题目
1.4.5 给出下面这些量的近似：
1.4.5 Give tilde approximations for the following quantities:
a. N + 1
b. 1 + 1/N
c. (1 + 1/N)(1 + 2/N)
d. 2N3 - 15N2 + N
e. lg(2N )/lg N
f. lg(N2 + 1) / lg N
g. N100/ 2N
分析
我们先看一下近似的概念
对数函数的运算法则
1.两个正数的积的对数，等于同一底数的这两个数的对数的和，即
2.两个正数商的对数，等于同一底数的被除数的对数减去除数对数的差，即
3一个正数幂的对数，等于幂的底数的对数乘以幂的指数，即
4.若式中幂指数则有以下的正数的算术根的对数运算法则:一个正数的算术根的对数，等于被开方数的对数除以根指数，即
然后我们一个个分析
a. N + 1
令g(N) = N + 1，则~f(N) = N,增长的数量级为N
b. 1 + 1/N
令g(N) = 1 + 1/N，则~f(N) = 1,增长的数量级为1
c. (1 + 1/N)(1 + 2/N)
令g(N) = (1 + 1/N)(1 + 2/N) = 1 + 3/N + 2/N2,则~f(N) = 1,增长的数量级为1
d. 2N3 - 15N2 + N
令g(N) = 2N3 - 15N2 + N ,则~f(N) = 2N3 ,增长的数量级为N3
e. lg(2N )/lg N
令g(N) = lg(2N )/lg N ,则~f(N) = lgN ,增长的数量级为 lgN
f. lg(N2 + 1) / lg N
这个有个地方需要注意，跟其他的有点不一样，因为 lg(N2 + 1) / lgN > lgN2 /lg N== 2，因此~f(N) = 2，增长的数量级为 2
g. N100/ 2N
这个也有点小窍门，就是分子分母同时取lg为底的对数，得到g(N) = (100 /( N * lg2))lgN，则~f(N) = lgN /N ，增长的数量级为lgN
答案
a. N + 1
~ N
b. 1 + 1/N
~1
c. (1 + 1/N)(1 + 2/N)
~ 1
d. 2N3 - 15N2 + N
~ 2N3
e. lg(2N )/lg N
~ lgN
f. lg(N2 + 1) / lg N
~ 2
g. N100/ 2N
~ lgN /N
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
