《算法基础讲座》part1

时间：2009-11-12 16:30

地点：JE群9770785     extjs群88403922     sm.net群75462710

 

各位群友，大家好。

今天开始，我将和大家聊聊基础算法。

欢迎大家和我一些学习或是复习一些很基础的东西。

共同讨论，共同进步。

 

 

一 什么是算法

 

算法是什么呢？

计算的方法

算法英文是algorithm，和算术arithmetic很像。

算法的本质就是更合理的计算。
不过这个计算的主体，不是人，而是机器，一般特指计算机。

要搞清楚算法到底是什么，有什么特点，就得先谈谈为什么会有算法。

我们知道，计算机上最基本的可调用的硬件资源是cpu和内存硬盘。

其中cpu直接执行指令，内存硬盘用来保存数据。

程序就是指令和数据的结合体。

这样，一个问题就出现了，对于既定问题，如何更有效的利用现有的资源，优化指令和数据本身。

这样，算法的一个基本概念就讨论出来了：研究计算机计算问题的计算过程和数据结构。

而算法本身就成了一门优化上面的两个研究对象的学科。

这个两个研究对象，对应到具体算法上专有名词，就是算法的时间和空间。
或者说是时间复杂度和空间复杂度。

优化计算过程就是降低算法的时间复杂度，单位时间内更高效的利用cpu的处理能力。
优化数据的存储结构，就是减低算法的空间复杂度，更有效的利用存储空间。

算法学科的所有问题和理论都是围绕着这两个问题展开的。

为了防止某些童鞋抠字眼，我得声明下，很多情况下，牺牲时间换空间和牺牲空间换时间很常见，例如cache。

ok，清楚了算法的本质和概念后，我们再讨论算法的特点。

 

 

 

二 基本数据类型

 

cpu和存储中使用的数据，都是二进制的，一般是俺byte为单位的。

而一般情况下，编程语言中定义的基本类型有：bool byte char int long float double String.

刚才我们说了，计算机处理的是bit或byte

所以需要将各种不同的类型映射到byte上。

即用byte来表示各种不同类型的数据。

如果说算法是一座大厦，那么数据结构就是一块块的砖和石头，里面的骨架和结构，就是计算过程。

我们继续说基础的数据结构。

我们刚才说道不同类型的数据要用byte来表示。

如何表示呢？这就是编码，可以认为就是通过某种方式，将数据中的信息映射到指定的byte中去。

比如int，一般用4个byte表示。第一位是符号位，后面是2进制整数的数位。

float很复杂，一般是1 8 23表示法。

第一位是符号位，8位是指数，23位是2进制的有效数字。

所以，不能直接在这个有效数字内表示的小数，都不能精确表示，比如1/3之类的。

而这个范围内表示的最小的一个精确值，就是float里，最接近0的一个数字，float能表示的数，除了0本身，没有能比他更小的了。

一般来说，char本身就是byte
如果按数值输出就是0-255，如果按character输出，就是ascii

string的表示就复杂的多。还是因为编码。

同一句话，不同的人说有不同的意思。同一个字符串，不同的编法，就有不同的码。

字符串一般可以用char的集合来表示（如果char可以包括非ascii字符的话），或是byte数组表示。

例如每一个汉字，在某个字符集中的内码是xxxx，俺某种编码表示为2个byte，（高低位的问题需要约定），那么一个字符串就能确定的表示成一个byte数组。

喜欢哲学或是数学的朋友，可以认为都是映射反演。一切编程和其他的人类活动，都是RMI。

relation mapping inversion

通过将有用信息提取出来，映射成可以直接处理的形式，处理完毕后，再翻译成本来的语义。

也可以用语言来类比，256个byte值，就是笔画或是字母。

不同的组合方式，抽象出来一些基本概念，基本概念再组合和包装，就成了一些高级概念。

刚才我们说了一些基本数据类型，其实还有一个特殊的基本类型。

那就是数组，其实更合适的说法叫基本结构。

为什么数组会成为基础结构呢，那是因为存储方式决定的，存储中的数据是一块块的。一次其实取了一块。就更一般的说，取连续的可知的一系列数据片段显然是最快的。
回复

数据存储是数据库设计的重要课题，我们会慢慢的讲到二叉树，查找树，红黑树，B*树。

好了，今天我们就讲到基本的数据结构。基本数据结构是编程语言和算法的基石。通过基本的数据结构，我们可以构建更复杂更抽象的结构。
有兴趣的朋友，可以看看相关的语言中的实际数据类型。明白表示方法，就清楚了数据类型的基本知识。比如最大值，最小值，为什么float不精确等等，善于思考的同学也可以设计自己的数据类型，比如具有更高精读的float（例如.net中没有BigXXX类，.net选手可以去实现，估计几十行代码就能实现常用的运算法则）。

下课。

 

Smith:推荐一些资料看看

看书很有效，但是比较苦，推荐《算法导论》。

 

感谢同步信息的剑鱼同学的无私劳动。

评论

4 楼 qbq 2009-11-19  

占位等待下一讲

3 楼 dandy 2009-11-16  

恩，不错，就是有点少，还没看尽兴！

2 楼 hedajia 2009-11-15  

期待楼主持续更新中

1 楼 libo_591 2009-11-13  

很好的知识，谢谢