《算法导论》读书笔记2(复杂度的表示，递归，以及概率）

 这两天终于把第一部分（基础知识）给过了一遍，算是热身啦。

 

第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% (还是很低？ 比十分之一高多了）

 

 不过这在现实中不这么有用， 现实中我们有太多的先验知识，让我们知道什么样的麦穗是大的。什么样的钻石是好的。

 

所以麦田问题在现实中又上升到哲学层次，是知足常乐呢， 还是要就要最好的， 这就要看每个人自己啦）