解决问题的步骤，方法
给你一个有序的数组： [-10,8,20,35,70,1000]
find:
线性查找
find2:
二分查找 -- 前提： 必须是有序的数组
怎么找中间数：
1-3 --2
3-9
3 4 5 6 7 8 9 --6
2-6
2 3 4 5 6 --4
3-8
3 4 5 6 7 8 5,6 约定：取中间数 偏左 - 5
start end -> Math.floor( (start+end)/2)
n个数 最少找几次 最多找几次 平均找几次
线性查找 1 n n/2
二分查找 1 log(2)n log(2)n/2 //log以2为底n的对数
4 2
8 3
16 4
数量级 线性查找平均次数 二分查找平均次数 倍数
100 50 3.5 14
10000 5000 7 714
10W 5W 9 5000倍
1亿 5000W 13 384W
程序比较：
find: 11000
find2: 40
二分， 分治 -- 分而治之
分治法： 可以解决绝大多数算法问题
找最小值：一分为二，left=递归左最小，right=递归右最小，比较left和right返回
数组去重：一分为二，left递归去重，right递归去重，循环right，如果不在left里，加到left，返回left
排序算法：
1）冒泡排序
比较相领的两个值，如果后面的小于前面的，就交换位置
2）选择排序（插入排序）
从剩余的数据中，找最小的，放到前面（和当前交换位置）
3）归并排序
分治法，二分法，左边排序自己，右面排序自己，每次比较左右数组第一个，小的扔到新的数组里面
4）快速排序
二分法，中间一刀，两个结果数组，分别放左右，递归调用，连接数组,c=arr.splice(cIndex,1),c[0]是中间数组
数据结构：
算法，离不开数据结构
有序的数组--数据结构
无序的数组--数据结构
算法，没有最好的算法，有最合适的算法
何为好坏：
衡量算法好坏，两个指标：
时间：时间复杂度 O(log(2)n)
空间：空间复杂度 S
分析不同数据结构
数据，增 修改 删除 查询
前提：数据不重复
增 查 综合
无序数组 50 39 85
有序数组 5000 5 5100
二叉树 25 12 35
散列 240 75 340
二叉树：
[ 56,49,62,70,76,2 ]
散列：哈希 hash
数组 存数据时，就用下标
例 ： 5--->arr[5]
3--->arr[3]
数n % arr.length ---> 目标位置
算法
一天学不会
html,js 2年
PHP 3-4 年
JAVA 5-6年
算法 10+ 年
算法 和 语言无关
网友评论