算法入门

共计 6048 个字符，预计需要花费 16 分钟才能阅读完成。

一. 算法的定义
任何代码片段都可以被称作是算法, 这也就是说算法其实就是完成一组任务的指令. 算法的优点在于要么速度很快, 要么解决一些很有趣的问题, 要么兼而有之. 并且算法可以应用于任何编程语言中.
二. 什么人适合学算法
学算法的人必须要懂得一定的数学知识, 具体点就是线性代数的知识. 只要你能做出这样一道题, 那么恭喜你, 可以学算法.
f(x) = x * 10;f(5) = ?;

三. 二分查找
假设存在一个有序列表, 比如 1,2,3…100. 如果我要你猜测我心中所想的数字是这个有序列表中的哪个数字, 你会怎么猜呢?
最简单的办法就是从 1 到 100 挨着猜, 这样一算, 那么很明显, 假如我想的是数字 100, 你有可能就要猜 100 次. 如此一来, 岂不是很浪费时间.
那么, 同样的道理, 如果在一行有 100 个字符的字符串中查找某个字母, 你是不是也要查找 100 次呢?
其实有更快速的办法, 就第一个例子而言, 试想, 如果我们第一次就把 100 拆一半, 也就是 50, 然后猜测 50, 根据我的回答来做下一步的确定. 也许我回答小了, 那么猜测的范围就会在 50 到 100 之间了, 如果是大了, 那么猜测的范围也就到了 1 到 50 之间, 依次类推, 我们把每次猜测都分成一半, 即 100 -> 50 -> 25 -> 13->7->4->2->1, 如此一来, 我们最多猜 7 次就能猜中我心中想的数字.
像这样的把元素分一半来查找就叫二分查找. 而通过二分查找实现的算法就叫二分算法, 简称二分法.
一般地, 我们把包含 n 个元素的列表, 用二分查找最多需要 log2^n 步.
也许你可能不记得对数的概念了, 但你应该记得幂的概念. 而对数 log10^100 相当于将多少个 10 的乘积结果为 100. 答案自然是 2 个, 即 10*10=100. 因此 log10^100 = 2;
总的来说, 对数就是幂运算的逆运算.
仅当列表有序的时候, 我们才可以用二分法来进行查找吗? 那倒不一定, 其实我们可以将这些列表的元素存储在一个数组中, 就好像, 我们把一个东西放在桶里一样, 然后给这些桶标上顺序, 而顺序则是从 0 开始编号的, 第一个桶是 0, 第二个桶是 1, 依次类推.
比如有这样一个有序数组[1,2,3…100]; 我想要查找 75 这个数字的索引, 很明显 75 这个数字对应的索引就是 74. 我们可以使用二分法编写代码, 如下(这里以 JavaScript 代码为例, 其它语言的代码也可以的):
var arr = [];
for(var i = 1;i <= 100;i++){
arr.push(i);
}
var checknum = 75;
// 定义第一个索引与最后一个索引
var low = 0;
var high = arr.length – 1;
// 我们查找数字只能在两者之间查找, 使用循环, 只要范围没有缩小到只剩一个元素, 都可以继续使用二分法拆成一半来查找
while(low <= high){
// 索引取一半, 如果不是整数则向下取整
var center = Math.floor((low + high) / 2);
// 最终结果一定是索引所对应的元素
var result = arr[center];
// 判断结果是否等于想要的结果
if(result === checknum){
console.log(center);
}else if(result < checknum){
// 如果取得索引对应元素值小于猜的值, 则修改最低索引的值, 以缩小猜测范围
low = center + 1;
}else if(result > checknum){
// 如果取得索引对应元素值大于猜的值, 则修改最大索引的值, 以缩小猜测范围
high = center – 1;
}else{
console.log(null);
}
}

得出最终结果就是 74.
我以如下图来展示上例代码的算法:
因此我们可以封装成一个函数, 传入参数就是一个数组和数组元素对应的值. 如下:
function getArrIndex(arr,result){
var low = 0,high = arr.length – 1,center = Math.floor((low + high) / 2);
while(low <= high){
if(arr[center] === result){
return center;
}else if(arr[center] < result){
low = center + 1;
}else if(arr[center] > result){
high = center – 1;
}else{
return ‘ 没有这个索引值 ’;
}
}
}
// 测试
getArrIndex([1,4,6,8,10],6);//2

四. 大 O 表示法
在算法入门之一中, 我总结到二分算法, 并且在二分算法中也提到过运行时间. 一般说来, 我们在写程序时都会选择效率最高的算法, 以最大限度的减少运行时间或者占用空间.
前面二分算法中说到, 如果挨着简单的查找从 1 到 100 的列表, 最多需要猜测 100 次, 如果列表的长度更大呢? 比如是 1 亿, 那我们就要猜测 1 亿次. 换句话说, 最多需要猜测的次数与列表长度相同, 这样所用到的时间, 我们称之为线性时间.
而二分查找则不同,100 次我们仅需猜测 log2^100 ≈ 7 次. 而如果是 1 亿, 我们也只需猜测 log2^100000000 ≈ 26 次. 这样通过二分查找所需要的时间, 我们称之为对数时间.
我们可以利用一种特殊的表示法来表示这种运行时间, 即大 O 表示法. 大 O 表示法指出算法的速度有多快.
在了解什么是大 O 表示法之前, 我们先来看一个例子:
假设有 100 个元素的列表, 我们使用二分查找大约需要 7 次(因为 log2^100≈7), 如果每一次大约为 1 毫秒. 二分查找就需要 7 毫秒, 而简单查找呢? 简单查找就需要 100 毫秒, 大约是二分查找的 15 倍左右.
那么假如有 1 亿个元素的列表呢, 使用简单查找就是大约 1 亿毫秒, 而二分查找则需要 26 毫秒 (log2^100000000) 左右就可以了. 如此一来, 简单查找比二分查找慢的多, 而且简单查找足足是二分查找的将近 400 万倍.
这说明一个什么问题呢?
这说明算法的运行时间是以不同的速度增加的, 也就是说随着元素的增多, 二分查找所需要的额外时间并不多, 而简单查找却要多很多. 我们把这种情况称之为增速. 仅仅知道算法的运行时间是不行的, 我们还需要知道运行时间随着列表的增加而增加, 即增速, 大 O 表示法的用武之地就在于此.
一般的, 拥有 n 个列表, 简单查找需要执行 n 次操作, 我们用大 O 表示法表示为 O(n). 当然单位不一定是毫秒或者秒, 大 O 表示法也就指出了算法的增速. 而使用二分查找, 我们可以表示为 O(log2^n).
再比如一个示例: 假设我们要画一个 16X16 的网格图, 简单查找就是一个一个的画, 结果需要画 256 次. 而如果我们把一张纸对折, 再对折, 再对折, 再对折, 每对折一次, 格子数就会增加, 对折一次画一次, 如此一来, 顶多需要 log2^256, 也就是 8 次就可以画出来.
我们用大 O 表示法, 就可以表示成: 简单查找为 O(n)的运行时间, 而 O(log2^n)则是二分查找所需时间.
大 O 表示法指出了最糟情况下的时间. 什么意思呢? 再看一个示例:
如果你要在一本书中使用简单查找查找一篇文章, 所需要的时间就是 O(n). 这意味着在最糟糕的情况下, 必须查找一本书中的每一页. 如果要查找的文章刚好在第一页, 一次就能找到, 那么请问简单查找的运行时间是 O(1)还是 O(n)呢? 答案自然是 O(n)呢. 因为大 O 表示法指出了最糟糕情况下的运行时间. 如果只用 1 次就能翻到, 那这是最佳情况.
从这些案例当中, 我们得出了如下结论:
1. 算法的速度指的并非时间, 而是增速。2. 谈论算法的速度时, 我们应该说的是随着速度的增加, 运行时间将以什么样的速度增加。3. 算法的运行时间用大 O 表示法表示。4.O(log2^n)比 O(n)快, 当搜索的元素越多, 前者快的越多。
事实上, 还有另一种算法. 即 O(!n). 也就是阶乘算法。来看一个案例: 假如一个人要去 4 个城市旅行, 并且还要确保旅程最短. 利用排列与组合的知识得出, 前往 4 个城市大约需要执行 24 次操作, 而如果是 5 个城市, 则大约需要执行 120 次操作. 也就是说随着城市的增加, 大约需要执行!n 次操作. 虽然这确实是一种算法, 但这种算法很糟糕。
五. 选择排序算法
在理解选择排序算法的原理之前，我们需要了解大 O 表示法，数组与链表等概念。
经常与计算机接触，相信都会听到内存这一个词，那么何为内存呢？我们用一个很形象的比喻来说明这个问题。
假设有一个柜子，柜子有很多抽屉，每个抽屉能放一些东西。也就是说，当我们往抽屉里放东西的时候，柜子就保存了这些东西。一个东西放一个抽屉，两个东西放两个抽屉。计算机内存的工作原理就如此，计算机的内存更像是许多抽屉的集合。
需要将数据存储到计算机中，你会请求计算机提供存储空间，然后计算机就会给你一个存储地址。在存储多项数据的时候，有两种数据结构，计算机可以存储，那便是数组和链表。
数组就是一系列元素的列表集合。比如，你要写一个待办事项的应用程序（前端术语也可以说是 todolist）。那么你就需要将许多待办事项存储到内存中。使用数组意味着内存是紧密相连的，为何如此说呢？
数组的元素自带编号，每个元素的位置，我们也叫做索引。例如:
[10,20,30,40]这一个数组，元素 20 的索引或者说所处的位置是 1。因为数组的编号都是从 0 开始的，这可能会让很多新手程序员搞不明白。几乎所有编程语言对数组的编号都是从 0 开始的，绝对不止 JavaScript 这一门语言。
假设，你要为以上 [10,20,30,40] 再添加一个元素，很明显，利用 JavaScript 提供的数组方法，你只能在之前或者最末又或者中间插入元素。但在内存中却不是这样。还是用一个比喻来说明。
相信每个人都有看电影的经历，试想当你到了电影院之后，找到地方之后就坐下，然后你的朋友来了，本想靠着你坐，但是靠着你的位置都被人占领了。你的朋友就不得不转移位置，在计算机中，请求计算机重新分配一个内存，然后才能转移到另一个位置。如此一来，添加新元素的速度就会很慢。
那么，有没有办法解决呢？
似乎，很多人都这样做过，由一个人占领位置之后，然后把旁边的预留座位也给占领，不仅仅是在电影中，在公交车上抢座位也是如此。这种办法，我们暂且称之为 ” 预留座位 ”。
这在计算机中也同样适用。我们在第一次请求计算机分配内存的时候，就请求计算机分配一些空余的内存，也就是 ” 预留座位 ” 出来。假定有 20 个 ” 预留座位 ”，这似乎是一个不错的措施。但你应该明白，这个措施，也存在缺点:
你额外请求的位置有可能根本就用不少，还将浪费内存。比如你选了座位，结果你的朋友没有来，其他人也不知道你的朋友不会来，也就不会坐上去，那么这个座位就空下来了。
如果来的人超过了 20 个之后，你预留的座位又不够，这就不得不继续重新请求转移。
针对这种问题，我们可以使用链表来解决。
链表也是一种数据结构，链表中的元素可存储在内存的任何地方。并且链表中 每一个元素都存储了下一个元素的地址，从而使一系列随机的内存串联在一起。
这就好像一个扫雷游戏，当你扫中一个，这个就会提醒你的四周格子有没有地雷，从而好作判断，让你是否选择点击下一个格子。因此，在链表中添加一个元素很容易：只需要将元素放入内存，并将这个元素的内存存储地址放到前一个元素中。
而且，使用链表还不用移动元素。因为只要有足够的内存空间，计算机就能为链表分配内存。比如如果你要为数组分配 100 个位置，内存也仅有 100 个位置，但元素不能紧靠在一起，在这样的条件下，我们是无法为数组分配内存的，但链表却可以。
链表好像自动就会说，“好吧，我们分开来坐这些位置”。
但链表也并非没有缺点。我们再做一个比喻：
假如你看完了一本小说的第一章觉得第一章不好看，想跳过几章去看，但并没有这样的操作，因为一般都是下一章下一章的看的，这意味着你要看第五十章，就要点下一章 49 次，这样真的很烦。（点目录不算）
链表也正是存在这一个问题，你在读取链表的最后一个元素时，你需要先读取上一个元素的存储地址，然后根据上一个元素的地址来读取最后这个元素。如果你是读取所有的元素，那么链表确实效率很高，但如果你是跳跃着读取呢？链表效率就会很低。
这也正是链表的缺点所在。但数组就不同，因为数组有编号，意味着你知道数组每个元素的内存地址，你只需要执行简单的数学运算就能推算出某个元素的位置。
利用大 O 表示法，我们可以表示将数组和链表的运行时间表示出来，如下:
数组 链表
读取: O(1) O(n)
插入: O(n) O(1)

其中 O(1)称作常量时间，O(n)则是线性时间。
如果你要删除元素呢？链表显然也是更好的选择，因为你只需要修改前一个元素指向的地址即可。
那么问题来了，数组与链表究竟哪种数据结构用的最多呢？
要看情况。但数组显然用的更多，因为数组支持随机访问。元素的访问有两种方式：顺序访问与随机访问。顺序访问意味着 你需要挨着顺序一个一个的访问元素，而随机访问这不必如此。因为数组有编号，所以在随机访问上，数组更能体现它的优势。
有了前面的知识，现在，咱们来学习选择排序算法吧！假设你的计算机存储了一些视频，对于每个视频的播放次数，你都做了记录，比如:
视频 1:50 视频 2:35 视频 3:25 视频 4:55 视频 5:60
现在，你要做的就是将播放次数从少到多按顺序排列出来。该如何做呢？
首先，你肯定需要遍历这个列表，找出播放次数最少的，然后添加到新的一个列表中去，并将这个添加的元素在原来列表中删除，然后，你再次这样做，将播放次数第二少的找出来，依次类推……
最后，你就会得到一个有序列表
视频 3:25 视频 2:35 视频 1:50 视频 4:55 视频 5:60
编写代码如下:
// 用一个数组表示播放次数即可
var arr = [50,35,25,55,60];
// 编写一个函数，参数传入排序的数组
function selectSort(arr){
// 获取传入数组的长度
var len = arr.length;
// 定义最小索引与数组每一项元素变量
var minIndex,ele;
for(var i = 0;i < len – 1;i++){
// 最小索引等于当前 i 值，相当于初始化值
minIndex = i;
// 初始化每一项
ele= arr[i];
for(var j = 1;j < len;j++){
// 获取相邻数，比较大小，得到最小数索引
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
// 将得到的最小数排列在最前面
arr[i] = arr[minIndex];
// 与最小数做比较的值放在最小数所处的位置
arr[minIndex] = ele;
}
return arr;
}
// 测试:
selectSort(arr);//[25,35,50,55,60]

下面我们来测试一下代码运行时间。对每个元素进行查找时，意味着每个元素都要查找一次，所以运行时间为 O(n), 需要找出最小元素，又要检查每个元素，这意味着又要 O(n)的运行时间。因此需要的总时间为 O(nxn)=O(n^2)。这也就是说，需要执行 n 次操作。
选择排序只是一种很灵巧的算法，但还称不上速度最快，速度最快的是快速排序法。