算法学习(一):算法和数据结构入门

这个系列主要是记录我的算法学习的笔记和总结, 可能更新的会比较慢, 毕竟我的主线是前端技术学习嘛

---

什么是算法

算法 就如他的名字一般, 完整描述如何得到想要的结果结果的方法, 是一系列解决问题的清晰指令,

举个例子, 比如我们想要计算1+2+3+4+...+100的结果, 我们有很多种方法

• 我们可以用最笨的方法,把他们一个一个加起来
• 我们也可用比较聪明的方法, 把第一项和最后一项相加, 然后乘以100, 再除以2

这些为了得到结果所以使用的方法就是我们所说的算法

算法有如下特征：

• 输入：一个算法必须有零个或以上输入量。
• 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
• 明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
• 有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
• 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

---

什么是数据结构

就是数据的结构

这里很多同学一定会疑惑, 数据还有结构吗？那么我们来举例说明吧

假如我们现在想列出家里都有哪些人, 那么我们该怎么列呢?

家族成员

再假设我们想我们想描述一个队伍的排队顺序和长度, 我们一般这么表示

排队

再假设我们想表示从地点1到地点5的路线, 我们可以这么表示

路线

这三种表现形式就对应着三种不同的数据结构,我们把第一种叫树, 第二种叫队列, 第三种叫图, 除了这三种之外还以后很多数据结构, 看吧, 数据还是有结构的吧？

---

算法和数据结构的结合

一般来说是这样的：

我们要解决一个跟数据相关的问题
分析这个问题，想出对应的数据结构
分析数据结构，想出算法
数据结构和算法是互相依存、不可分开的, 比如当你学习完排序算法，就能了解常见的数据结构

算法大分类

分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
线性规划法：自己google词条吧。
简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
我们前端主要使用分治法——分而治之。

---

伪代码和流程图

伪代码

在学习算法的时候, 我个人推荐用伪代码作为设计算法的手段, 所谓的伪代码其实就是一种不拘泥于任何语言的一种你自创的语法, 主要作用是表达出算法的过程,这样的好处就是你不用去纠结语法细节, 完全把注意力集中在算法实现上

假设我用js类似的语法格式作为我伪代码的格式

自定义的条件控制语句

if( 满足x条件) {
  console.log(1)
} else if(满足y条件) {
  consloe.log(2)
}else {
  console.log(3)
}

自定义的循环语句

a=0
for(i=0; i<5; i++) {
  console.log(a)
  a++
}

一个最简单的例子

从正整数数组a中找出最小的数字, 打印出来

这个问题的思路如下:

1. 我们假设数组的第一项为最小数字min
2. 第二项与第一项比较, 如果第二项比第一项小, 就把第二项的数赋值给min, 如果第二项比第一项大, 那么min仍然为第一项
3. 拿第三项和min比, 如果第三项比min小, 那min的值就是第三项的值, 如果第三项比min大, 那min值不变
4. 以此类推, 直到最后一项与min比完
5. 输出的min值就是数组中最小的值

代码如下

a = [23,29,39,49,59]
min = a[0]
index = 1
while(index < a.length) {
  if(a[index] < min) {
    min =  a[index]
  }
  index += 1
}
console.log(min)

流程图

简单来说流程图就是用图形的方式表达出程序执行的过程

如何画流程图

1. 流程图的开始我们一般用一个椭圆的start或开始表示
2. 用箭头连接每一条指令, 箭头的方向就是执行方向
3. 普通语句我们用方框表示
4. 分支我们用菱形表示, 并且在分支上标明分支条件
5. 结束我们通常用一个椭圆的end或者结束表示

流程图的好处是直观的用图形表现是我们的思路, 用来帮助我们理清思路是最合适不过的了

从正整数数组a中找出最小的数字我们用流程图表示的话, 就是下面这个流程图

流程图

---

算法小试牛刀

上面说了那么多概念, 估计大家也都烦了, 那么我们就开始搞几个简单的排序算法吧，这里我们用冒泡排序把一个数组按顺序从小排到大

冒泡排序算法

QQ20180321-202310.gif

1.从数组的起始位置开始,将相邻的两个数比较,如果前一个比后一个大, 则交换两个数的位置, 如果前一个比后一个小, 则位置不动, 这样一轮比完后, 数组最后一个数一定是数组中最大的那一个
2.再次从数组起始位置按照上面的方法两两对比, 这次比到数组的倒数第二个位置, 这时候倒数第二个就是整个数组第二大的数
3.以此类推, 直到比到数组第一个位置为止, 这样数组就从小到大依次排列了!

冒泡排序动画

冒泡排序算法的代码

let a = [45,2,17,99,60]

let loopTimes = 1
let length = a.length - 1

while(loopTimes < a.length) {
  for(let i=0; i < length; i++) {
    if(a[i] > a[i+1]){
      let t=a[i]
      a[i] = a[i+1]
      a[i+1] = t
    }
  }
  length -= 1
  loopTimes += 1
}
console.log(a)