`
bencode
  • 浏览: 106905 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

《算法导论》读书笔记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% (还是很低? 比十分之一高多了)

 

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

 

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

 

 

  • 大小: 20.5 KB
  • 大小: 8.3 KB
分享到:
评论
1 楼 bingjing12345 2012-08-03  

也就是说: 十颗钻石,我们要先看4颗, 然后看到一颗比前面多大的,就拿吧
估计楼主也没自己算。。。。。
这是不对的。  应该先看3颗。
double sum3 = 0;
for(int i=3;i<10;i++){
sum3 +=1.0/i;
}
System.out.println((3.0/10 )*sum3) ;
double sum4 = 0;
for(int i=4;i<10;i++){
sum4 +=1.0/i;
}
System.out.println((4.0/10 )*sum4) ;
output:
0.39869047619047615
0.3982539682539683
你帖子浏览量这么高,最好负责点。。。。。

相关推荐

Global site tag (gtag.js) - Google Analytics