0%

主要内容

由于概率算法在实际中用得不多,我先战略性地快速过完本章。

分析一个随机算法的运行时间时,输入值由随机数生成器产生,运行时间称为期望运行时间。指示器随机变量为概率和期望之间的转换提供了一个便利的方法,用于很多随机算法的分析中。

阅读全文 »

缘起

在知乎上看到一篇文章:如何下载50年前中国各地的高清卫星照片,网友们纷纷撰写了各地50年前卫星照片的解读文章。我也下载到了我的家乡——湖北黄冈在1970年的卫星地图,并做简要的解读。

市区变迁

黄州是黄冈市唯一的市辖区,也是市政府所在地。明代以后,蕲州(今蕲春县)划归黄州府管理,形成与当今黄冈市类似的行政格局,基本沿袭至今。因此,明清以来,黄州一直是鄂东黄冈地区的政治经济文化中心。本文介绍的就是黄州区的卫星地图。

阅读全文 »

主要内容

本章介绍的第一个算法求解最大子序列和问题,第二个算法求解矩阵乘法问题。递归式与分治法紧密相关,本章介绍三种方法求解递归式:代入法、递归树法和主方法。

最大子序列和问题

买股票问题可以转化为最大子序列和问题。只有当序列中包含负数,最大子序列和问题才有意义。

阅读全文 »

主要内容

本章讲解如何简化算法的渐近分析,介绍了几类渐近记号。最后简单介绍了常用函数的性质。本章的内容在这里描述得非常简略,但为了保持整个系列的完整性,还是贴出来了。

渐近记号

本章介绍了如下渐近记号,它们的严格定义分别如下:

阅读全文 »

主要内容

本章介绍了一个贯穿全书的算法设计与分析的框架。正文中介绍了插入排序和归并排序两种排序算法,以它们为例,介绍了用循环不变式证明算法正确性的方法和分治法的思想。还介绍了如何分析算法的运行时间。

插入排序

本书介绍的第一个算法是插入排序算法。插入排序的工作机理和很多人打牌时,整理手中牌时的做法差不多。它的基本思想是,通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。根据伪代码,给出如下的C语言实现:

阅读全文 »

主要内容

本章介绍了算法的定义、作用和重要性。

简单地说,算法(algorithm)是定义良好的计算过程。算法是一系列的计算步骤,用来将输入数据转换成输出结果。算法能够解决各种类型的问题,应用面很广。计算机的计算资源和存储资源是有限的,时间和空间上有效的算法能够有效地利用这些有限的资源。解决同一问题的不同算法,效率常常相差很大,这种效率上差距的影响往往比硬件和软件的差距还要大。拥有扎实的算法知识和技术基础对程序员来说非常重要。

阅读全文 »

下面是一个优秀的程序员应该掌握的基础知识以及较为靠谱的学习路线:

  • 计算机体系架构:读《深入理解计算机系统》,做完Lab Assignments
  • 数据结构与算法:读《算法导论》,做完习题
  • 操作系统:读《现代操作系统》和《操作系统概念》中的任何一本,跟着MIT 6.824课程,把xv6撸一遍
阅读全文 »

OpenGrok是跨平台、开源免费的源码阅读工具。OpenGrok生成源码的索引,Apache Tomcat提供Web服务,用户即可在浏览器中阅读代码,使用体验可以去看看这里。Linux下好用的源码阅读工具极少,OpenGrok可以一试。

本文是一篇没有技术含量的笔记,之所以贴出来是因为我找到的其它教程都失效了。

阅读全文 »

我的iPhone 5s手机服役四年,一直用得比较满意。但随着系统和应用的日渐臃肿,16G的容量太小了,时不时就警告存储空间不足,需要定期清理照片和软件缓存,实在是难受。于是我换了部华为P20手机。

安卓系统有很多方便之处,不需要下载一个废物软件(没错,说的就是你,iTunes)就可以传输文件,不需要越狱就能从软件包安装APP。另外,国内厂商定制的安卓系统本土化做得不错,诸如垃圾短信拦截、骚扰电话标注等功能非常实用。

阅读全文 »

智能手机越来越强大了,在国内出门带一部手机就能完成大部分事情。手机给生活带来便利的同时,也造成了很多问题,很多人花大量时间在手机上,随处可见“低头族”。无论男女老少,俨然成为手机的奴隶!

我也算半个奴隶,有时候,躺在床上刷刷网页,一两个小时就过去了,心里充满了悔恨。长期玩手机对健康很不好,特别伤颈椎和视力,而且手机上大部分信息没啥营养,养成频繁看手机的习惯会影响专注力。为了摆脱手机的奴役,我总结了下面一些原则:

阅读全文 »