这两天终于把第一部分(基础知识)给过了一遍,算是热身啦。
第3章:函数的增长
这一章主要讲了复杂度的表示方法:大O小O等。以及各类基本常用函数,像对数,指数。
当然还有阶乘,取整,取模函数。
还有学了计算机后才接触到的函数迭代以及 到处可见的斐波那切数
基本上算是把初等数学给温故了一遍。
第四章:递归式
在“笔记1”中, 我们实现了归并排序, 我们为了求比较次数,把算法简化成这样:
public int mergeSort2(int n) {
if (n == 0 || n == 1) {
return 0;
}
return 2 * mergeSort2(n / 2) + n - 1;
}
上面的函数,如果用数学公式表示,差不多是这样: T(n) = 2 T(n / 2) + n - 1
~~ 我知道这个复杂度差不多是 n log(n) , 可是这个怎么来的呢?
这一章就主要讲了三种解递归式的方法:
1。猜(偶没实力--男人不喜欢说没能力)
2。递归树。 这个无聊了画画倒是可以的, 好用, 就是累
3。主方法。提供几种“模式”去套, 这个很方便
(书上说要记忆,其实不用记, 关键是知道有这回事,到时候翻书就行)
其实上面的三种方法,对于大学的我可能还比较感兴趣,现在离学校的年代越来越远,离数学也越来越远。
我们程序员应该有更懒的方法,更直观, 就是把它画出来。
(记得高中时画的坐标轴吗? 直观。。现在我们用电脑画,呼 可不是PS)
工作了整一天,先直接看看程序的效果图哈:
用的是ruby, wxruby. 附件中有源码和exe文件可供下载(别扔鸡蛋,纯爱好)
现在谁快谁慢, 图中一目了然了。
要往软件中新添加一个函数也很容易, 只要写一个类,放在charts目录下即可。
像这样:
module Charts
class Log
def name
'log(n)'
end
def fun(x)
x > 0 ? Math.log(x) : nil
end
end
end
现在我来看看,那个递归式T(n) = 2 T(n/2) + n 是否真的接近于 nlog(n), 我把n设置得大一点, 这样让递归式的曲线更平滑。因为我的实现是只计算整数的。
和nlog(n)最接近, 就是它啦!
第五章:概率分析和随机算法
这一章内容很少, 毕竟大部分相关的东西可以在专门的概率论数学书中有。
主要是分析了几个例子,重在分析的思路。
不过有两个“打乱数组元素”的算法,需要写一下。 我是用ruby完成的。
第一个比较简单,当然也比较傻瓜, 时间复杂度更高些(要排序,所以复杂度和排序相当 nlog(n))
差不多像这样:
def shuffle(array)
array.sort_by { rand }
end
第二个差不多是这样:
def shuffle(array)
n = array.size
n.times { |i|
j = rand(n)
array[i], array[j] = array[j], array[i]
}
end
在O(n)时间内完成
这一章还分析了两个趣味题:生日悖论,还有在线雇用
其实同年同月同日生没这么难,只是和你同年同月同日生概率低一些 ,一堆人之中找出两个同样生日的,概率还是很高滴!
在线雇用这个问题本来不趣味,只是前段时间看到这个帖子
http://www.iteye.com/topic/534346
第一题像是:苏格拉底的麦田问题。
怎么样才能尽可能的摘到最大的麦穗呢? 只许前进, 只有一次机会~~
是个哲学问题,也是个数学问题。
有个想法: 前面先看几颗钻石,心中有个底,然后见到比前面最大的还要大的就选。
best = -1 # 钻石等级
# 先观察k颗, 以获取经验
k.times { |i|
if level(i) > best # 碰到更好的,记录它
best = level(i)
}
k.upto(n - 1) { |i|
if level(i) > best
return i # 选的就是它
}
那 k 到底是多少,才能让我们拿到最大棵钻石的概率最大呢?
书中详细的分析,可知道当 k = n / e 时, 概率最大化为 1 / e, (e大概是2.72)
也就是说: 十颗钻石,我们要先看4颗, 然后看到一颗比前面多大的,就拿吧, 这时候你拿到最大颗钻石的希望是:35% (还是很低? 比十分之一高多了)
不过这在现实中不这么有用, 现实中我们有太多的先验知识,让我们知道什么样的麦穗是大的。什么样的钻石是好的。
所以麦田问题在现实中又上升到哲学层次,是知足常乐呢, 还是要就要最好的, 这就要看每个人自己啦)
- 大小: 20.5 KB
- 大小: 8.3 KB
分享到:
相关推荐
中国科学技术大学 算法导论 课件 计算机相关专业必修
算法时间复杂度分析中递归方程求解方法综述
关于递归算法时间复杂度分析的探讨.pdf
中国科学技术大学 算法导论 课件 计算机相关专业必修
Java数组(冒泡,选择,插入希尔)递归算法的复杂度
《算法导论(原书第2版)》深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。《算法导论(原书第2版)》的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的...
递归方程组解的渐进阶的求法,算法时间复杂度,迭代算法,递归算法,母函数法,套用公式法,迭代树法
MIT算法导论公开课之课程笔记 2.渐进符号、递归及解法.rar
此代码展示了一种用递归解决迷宫问题的方法,可以自行输入迷宫即得到解答
《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析...
对算法进行时间复杂度分析是算法分析与研究 的重要内 容, 而...提出了用组合数学中的母函数与递推关系理论来分析一些特 殊的递归算法的 时间复杂度, 并 同时得出三个 推论, 在算法 的 分析与研究方面具有一定的参考价值
实现了算法导论第六版,第四章77页的递归方形矩阵相乘,代码中保留了编写中遇到的错误和尝试记录,通过代码自己更好的理解了new,和局部变量的生命周期.还有一个打印int数组的函数。
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析...
NULL 博文链接:https://deepin.iteye.com/blog/1390131
ACM 参考书 算法导论中文版第4章 递归式相关内容 ACM 参考书 算法导论中文版第4章 递归式相关内容
《算法导论(原书第2版)》深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。《算法导论(原书第2版)》的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的...
本书是原书的第2版,在第1版的基础之上增加了一些新的内容,涉及算法的作用、概率分析和随机化算法、线性规划,以及对第1版中详尽的、几乎涉及到每一小节的修订。这些修订看似细微,实际上非常重要。书中引入了...