时间: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:推荐一些资料看看
看书很有效,但是比较苦,推荐《算法导论》。
感谢同步信息的剑鱼同学的无私劳动。
分享到:
相关推荐
算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础算法基础
算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用数据结构和算法).part1.rar算法导论(中文版)(现代计算机常用...
零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1 零基础学算法.part1
matlab算法大全-算法大全.part1.rar 本帖最后由 nisky 于 2012-4-17 23:42 编辑 算法大全.part4.rar 算法大全.part3.rar 算法大全.part2.rar ...
算法设计与分析基础.part1 算法设计与分析基础.part1
计算机动画的算法基础part5,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
计算机图形学的算法基础,教程
算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用数据结构和算法).part3.rar算法导论(中文版)(现代计算机常用...
本书对计算机图形学和其他领域的二维和三维几何学算法进行了全面的解析和合理的组织。... 计算机图形学几何工具算法详解.part1.rar 计算机图形学几何工具算法详解.part2.rar 计算机图形学几何工具算法详解.part3.rar
计算机图形学的算法基础,教程
计算机动画的算法基础part3,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
计算机图形学的算法基础,教程
【原 书 名】 Procedural Elements for Computer Graphics (2E) 【作 者】 (美)David F.Rogers 【译 者】 石教英 彭群生 本书从图形学最基础的光栅扫描、区域填充、画直线和圆弧等算法讲起,详细...
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程
计算机图形学的算法基础,教程
计算机动画的算法基础part2,共6部分 国家九五重点图书 鲍虎军,金小刚,彭群生著 浙江大学出版社
算法设计与分析基础.part2 算法设计与分析基础.part2
算法设计与分析基础.part3 算法设计与分析基础.part3
计算机算法基础课后习题答案,华中科技大学出版的第三版计算机算法第四、五、六、八章课后习题答案,对计算机专业考研复试的学生很有用哦……