L3F.WIN

Github及Hexo的使用

0%

算法图解

算法图解

======================================

算法简介

二分查找

二分查找能解决什么问题?

有序的元素列表中快速的找到指定元素位置。使用二分查找可以将查找步骤减少到 $log_2n$ 步

二分查找的原理

通过猜测中间的数字,从而每次都将余下的数字排除一半,从而减少查找的次数

对应JS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var binary_search = function(list, item){
var low = 0;
var high = list.length - 1;

while(low <= high){
var mid = Math.ceil((low + high)/2); //二分查找的关键点
var guess = list[mid];
if(guess == item){
return mid;
}else if(guess > item){
high = mid - 1;
}else{
low = mid + 1;
}
}
return "none";
}
console.time("时间"); //测试运行时间
my_list = [1,3,5,7,9,11,13,15,17,19];

$('div').text(binary_search(my_list, 17));
console.timeEnd("时间");

练习

  • 假设一个包含128个名字的有序列表,你要是用二分查找在其中查找一个名字,请问最多需要几步才能找到 (7步)
  • 上面列表的长度翻倍后,最多需要几步? (8步)

大O表示法

大O表示法是一种特殊的表示法,指出了算法的速度有多快。大O表示法指出了算法有多快,需要执行的操作数。

一些常见的大O运行时间

  • $O(log,n)$,也叫对数时间,这样的算法包括二分查找。
  • $O(n)$,也叫线性时间,这样的算法包括简单查找。
  • $O(n * log n)$,这样的算法包括快速排序。 一种速度较快的排序方法
  • $O(n^2 )$,这样的算法包括选择排序。 一种速度较慢的排序方法
  • $O(n!)$,这样的算法包括接下来将介绍的旅行商问题的解决方案。 一种非常慢的算法

使用这几种算法绘制一个16格的网格需要的时间如下:
大O表示法

小结

  • 二分查找的速度比简单查找快的多。
  • $O(log,n)$比$O(n)$快。需要搜索的元素越多,前者比后者就快得越多。
  • 算法运行时间并不以秒为单位。
  • 算法运行时间是从其增速的角度度量的。
  • 算法运行时间用大O表示法表示

选择排序

数组与链表的区别

链表

  • 链表中的元素可以存储再内存的任何地方
  • 链表的每个元素都存储了下一个元素的地址
  • 链表的优势在于插入元素方面。
  • 链表的读取速度很慢
  • 链表更适合中间插入数据(只需要修改他前面的元素指向的地址)
  • 链表更适合删除元素

数组

  • 数组中的内存必须是相连的。
  • 数组的效率很高。
  • 数组对内存的使用效率较低

数组和链表的读取插入运行时间
数组和链表操作运行时间

选择排序

将混乱的排序,按照一定的顺序进行排序,排序所需要的总时间为 $O(n^2)$。

选择排序应用

  • 电话簿中的人名
  • 旅行日期
  • 电子邮件

选择排序的优缺点

虽然选择排序是一个灵巧的算法,但其速度不是很快,下章的快速排序速度更快,请运行时间为 $O(n,log,n)$。

对应JS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var findSmallest = function(arr){
var smallest = arr[0];
var smallest_index = 0;
for(var i = 0; i < arr.length; i++){
if(arr[i] < smallest){
smallest = arr[i];
smallest_index = i;
}
}
return smallest_index;
}

var selectionSort = function(arr){
var newArr = [];
var arrL = arr.length;
for(var i = 0; i< arrL; i++){
var smallest = findSmallest(arr);
newArr.push(arr[smallest]);
arr.splice(smallest,1);

}
return newArr;
}

console.log(selectionSort([5,3,6,2,10]));

小结

  • 计算机内存犹如一大堆抽屉
  • 需要存储多个元素时,可以使用数组或链表
  • 数组的元素都在一起
  • 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
  • 数组的读取速度很快
  • 链表的插入和删除速度很快
  • 在同一个数组中,所有元素的类型必须相同

递归

如何选择

如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。

基线条件和递归条件

每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。

对应js代码

1
2
3
4
5
6
7
8
9
var fact = function(x){
if(x == 1){
return 1;
}else{
return x * fact(x-1);
}
}

console.log(fact(5));

小结

  • 递归指的是调用自己的函数
  • 每个递归函数都有两个条件:基线条件和递归条件
  • 栈有两种操作:压入和弹出。
  • 所有函数调用都进入调用栈。
  • 调用栈可能很长,这将占用大量的内存。

快速排序

分而治之(divided and conquer,D&C)

D&C算法来分土地

① 找出基线条件,尽可能的简单
② 不断讲问题分界,或者说缩小规模,使其满足基线条件

使用循环完成数组内数字相加js代码

1
2
3
4
5
6
7
8
9
var arr = [2,4,6];
function sum(arr1){
var total = 0;
for(var i=0; i< arr.length; i++){
total = total + arr[i];
}
return total;
}
console.log(sum(arr));
使用递归JS代码
1
2
3
4
5
6
7
8
9
var arr = [2,4,6];
function sum(arr1){
if(arr1.length == 0){
return 0;
}else{
return arr1[0] + sum(arr1.slice(1));
}
}
console.log(sum(arr));

练习3 找出数组中最大的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [1,3,5,7,9,11,13,15,17,19];
function compare(arr1){
if(arr1.length == 2){
return arr1[0] > arr1[1] ? arr1[0]:arr1[1];
}else{
var sub_max = compare(arr1.slice(1));
if(arr1[0] > sub_max){
return arr1[0];
}else{
return sub_max;
}
}
}
console.log(compare(arr));

快速排序