关于算法的简单应用

解决问题的步骤，方法

给你一个有序的数组：  [-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+  年

算法  和 语言无关