乐趣区

计算机科学基础_4

算法入门

选择排序,Selection sort
大 O 表示法,Big O notation
归并排序 – Merge sort
Dijkstra 算法

写指数函数,只是无数解决方案的一种,还有其它方案。用不同顺序写不同语句,也能得到一样的结果,不同的是“算法”,意思是:解决问题的具体步骤。即使结果一致,有些算法会更好。一般来说,所需步骤越少越好。不过有时候也会关心其他因素,比如占多少内存。
“算法”一词来自 阿尔●花拉子密,1000 多年前的代数之父之一。如何想出高效算法,是早在计算机出现之前就有的问题,诞生了专门研究计算的领域,然后发展成一门现代学科,计算机科学。
选择排序
记载最多的算法之一是“排序”。比如给名字,数字排序。排序到处都是,找最便宜的机票,按最新的时间排邮件,按姓氏排联系人等等,这些都要排序。计算机科学家花了数十年发明了各种排序算法,还起了酷酷的名字,“冒泡排序”,“意面排序”,“选择排序”
比如:一堆机票价格,都飞往目的地。把价格一组数据存放到一个数组结构。先找到最小数,从最上面开始,然后和第一个比较,所以看最小的数是否变化,移动位置。重复循环比较,持续移动位置。意味着,如果要排 N 个东西,要循环 N 次,每次循环中再循环 N 次,共 N *N。

算法的输入规模和运行步数之间的关系,叫算法的复杂度。表示运行速度的量级。计算机科学家们把算法复杂度叫:大 O 表示法(big O notation)。
选择排序的算法复杂度 O(n^2)效率不高。
归并排序
第一件事是检查数组大小是否 >1,如果是,就把数组分成两半。再检查数组大小是否 >1, 如果是,继续分组,如果不是开始“归并”。从前两个数组开始,读第一个(也是唯一一个)值,然后开始比较,如果更小,排在之前。重复这个过程,按序排列。然后数组大小增加,再次归并。同样,取前二个数组,比较第一个数,然后再比较第一个数组的第一个数,第二个数组的第二个数。然后合并成更大有序的数组。直到排序完整。
归并排序的算法复杂度 O(n * logn),n 是需要比较 + 合并的次数和数组大小成正比,logn 是合并步骤的次数。
图搜索

“图”是用线连接起来的一堆“节点”。可以想成地图,每个节点是一个城市,线是公路。一个城市到另外一个城市,花的时间不同,可以用成本 (cost) 或权重 (weight) 来代称,代表要几个星期。假设想找“高庭”到“凛冬城”的最快路线。最简单的方法是尝试每一条路,计算总成本。这是“蛮力办法”。
假设用蛮力方法,来排序数组,尝试每一种组合,看是否排好序。这样的时间复杂度是: O(n!),n 是节点数,n! 是阶乘。比 O(n^2)还糟糕。
从“高庭”开始,此时成本为 0,把 0 标记在节点里,其它城市标记成问号,因为不知道成本多少。Dijkstra 算法总是从成本最低的节点开始,目前只知道一个节点“高庭”,所以从这里开始,跑到所有相邻节点,记录成本,完成一轮算法。但是还未到“凛冬城”,所以再跑一次 Dijkstra 算法。下一个成本最低的节点,是“君临城”,记录相邻节点的成本,到“三叉戟河”,然而想记录的是,从“高庭”到这里的成本,所以“三叉戟河”的总成本 8 +5=13。现在走另外一条路到“奔流城”,成本高达 25,总成本 33,但“奔流城”中最低成本是 10,所以无视新数字,保留之前的成本 10。现在看了“君临城”的每一条路还没到“凛冬城”所以继续。下一个成本最低的节点,是“奔流城”,要 10 周。先看到“三叉戟河”成本,10+2=12,比之前的 13 好一点, 所以更新“三叉戟河”为 12,“奔流城”到“派克城”成本是 3。10+3=13,之前是 14,所以更新“派克城”为 13。“奔流城”出发的所有路径都走了遍,还没到终点,所以继续。下个成本最低的节点,是“三叉戟河”。从“三叉戟河”出发,唯一没看过的路,通往“凛冬城”。成本是 10 加上“三叉戟河”的成本 12,总成本是 22。再看最后一条路,“派克城”到“凛冬城”,总成本是 31。所以最佳线路是:“高庭”->“奔流城”->“三叉戟河”->“凛冬城”。

Dijkstra 的语录:“有效的程序员不应该浪费很多时间用于程序调试,他们应该一开始就不要把故障引入。”“程序测试是表明存在故障的非常有效的方法,但对于证明没有故障,调试是很无能为力的。”
Dijkstra 算法算法复杂度是:O(n^2)经过改造的 Dijkstra 算法复杂度减低为:O(n * logn + l) n 是节点数,l 是多少条线
数据结构

数组,Array
字符串,String
矩阵,Matrix
结构体,Struct
指针,Pointer
节点,Node
链表,Linked List
队列,Queue
栈,Stack
树,Tree
二叉树,Binary Tree
图,Graph

算法处理的数据,存在内存里的格式是什么。希望数据是结构化,方便读取,因此计算机科学家发明了“数据结构”。
数组
数组 Array,也叫列表(List), 或向量(Vector)。有一些区别,在不同语言中基本类似。
数组的值一个个连续存在内存里。可以把多个值存在数据变量里,为了拿出数组中的某个值,要指定一个下标 (index) 大多数编程语言中,数组下标都从 0 开始。用方括号 [] 代表访问数组。
j = [5, 3, 7, 21, 82, 4, 19]
a = j[0] + j[5]
数组存在内存里的方式,十分易懂。为了简单,假设编译器从内存地址 1000 开始存数组,数组有 7 个数字,像上图一样按顺序存。写 j[0],会去内存地址 1000,加 0 个偏移,得到地址 1000,拿值: 5。写 j[5],会去内存地址 1000,加 5 个偏移,得到地址 1005,拿值: 4。

数组的用途广泛,所以几乎所有的编程语言,都自带了很多函数来处理数组。
字符串
数组的亲戚是字符串 String,其实就是字母,数字,标点符号等,组成的数组。
计算机怎么存储字符? 通过字符对应的 ASCII 表
写代码时,用引号括起来就行了: j = “STAN ROCKS”
虽然长的不像数组,但的确是数组。
注意:字符串在内存里以 0 结尾,不是“字符 0”,是二进制“0”,这叫字符“null”, 表示字符串结尾。这个字符非常重要,如果调用 print()函数,会从开始位置,逐个显示到屏幕,但是得知道什么时候停止下来。否则会把内存里所有东西都显示出来。0 告知函数何时停下。

因为计算机经常处理字符串,所以有很多函数专门处理字符串。

退出移动版