没长正的技术专栏 勤动手、多思考

算法

2017-02-01
mzz

阅读:

2019-10-14

目的

了解数据结构、算法思想、优缺点、合理运用到项目中, 常见算法:

数据结构

了解各类数据结构在内存的存储模型。

数组

连续分配的存储区域(连续的内存空间)

如果没有足够连续分配的存储空间,则不能够成功常见数组对象。

特性:随机查找速度快 O(1),插入效率低O(n)  -->Why?

链表(单/双/循环链)

可以是非连续的存储区域(了解3类链表特点)

特性:顺序查找 O(n),插入、删除 O(1)  -->Why?

扩展:实例:点餐服务 ------> 插入、删除效率高

调用栈: 后进先出(先进后出)
调用栈可能很长,需要占用很多的内存     --->竖着的 长方形
不能用于查找

优化:采用循环、尾递归

扩展:思考代码中方法名称、参数名称 存放的位置

实例:递归算法、函数调用(JVM)、深度优先遍历、两个栈实现一个队列

队列

实例:公交车站,排队等车、系统中各个资源管理、消息缓冲区管理、广度优先搜索
特点:先进先出

散列表

 定义:根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访  	  问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
 
 内部机制: 实现、冲突、散列函数

 散列函数:
    <1.它必须是一致的(同一输入,输出结果相同)
    <2.它应将不同的输入映射到不同的数字 ** (没有冲突的情况) 很难

   (1)散列函数很重要(最理想的情况:将键均匀映射到散列的不同位置)
   (2)散列的链表不能太长,影响查询效率
   
   构造方法:
   	(1)直接定址法(关键码本身和地址之间存在某个线性函数关系时,散列函数取为关键码的线性函数,即:H(key)=a*key+b,a、b均为常数。)  查找表较小且连续,不常用
   	(2)除留余数法(通过选择适当的正整数p,按计算公式H(K)=K mod p来计算关键码K的散列地址。
)  常用:Integer等数据类型 源码中hashcode
	(3)平方取中法(将关键码K平方,取K^2中间几位作为其散列地址H(K)的值。
)
	(4)随机数法(采用随机函数作为散列函数H(Key)=random(Key),其中random为随机函数。)
        当关键码长度不等时,采用该方法较恰当。
        
    解决Hash冲突的处理方法:
    (1)再hash
    (2)缓冲区
    (3)开放定址法(从发生冲突位置的下一个位置开始寻找空的散列地址。发生冲突时,线性探测下一个散列地址是:Hi=(H(key)+di)%m,(di=1,2,3...,m-1))
    (4)拉链法()
    
 实例: HashTable、HashMap、加密算法、查找、海量数据处理

    <1.模拟映射关系 -->将散列用于查找 (通过姓名查询电话号码)
    <2.防止重复(投票站投票,不允许1人多投)
    <3.将散列用于缓存(网站缓存,不用每次请求服务器)

性能:

    1.较低的填充因子(散列包含的元素个数/位置总数)
    2.良好的散列函数(各个语言内置有散列函数)

图有节点和边组成。

概念: 邻接表、邻接矩阵、邻接点、度

有向图

有方向,单向关系

无向图

无方向

树是一种特殊的图。
实例:家谱

最小生成树:n个顶点的连通图中选择n-1条边,构成权值之和最小的连通子图,被称为最小生成树。

扩展:二叉树、B-树B+树红黑树、堆、伸展树。

算法

二分法查找

    有序的数组效率 O(logn)

    实例 猜数字 100 需要猜多少次 log128)

    对数与幂运算互为逆运算。(幂运算表示指数个底数相乘
    public class BinaryTest
    {
        public static int binary(int[] array, int value)
        {
            int low = 0;
            int high = array.length - 1;
            while(low <= high)
            {
                int middle = (low + high) / 2;
                if(value == array[middle])
                {
                    return middle;
                }
                if(value > array[middle])
                {
                    low = middle + 1;
                }
                if(value < array[middle])
                {
                    high = middle - 1;
                }
            }
            return -1;
        }
        public static void main(String[] args)
        {
            int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
            int value = binary(a, 9);
            System.out.println(value);
        }
    }

快速排序

D&C 分而治之的思想欧几里德算法辗转相除法   递归的思想

基线条件数组为空或者只有一个元素时  类似与初中时给函数并找规律

实例农场主分地问题  1680 X 640 --> 640 X 400 --> 240 X 400 --> 240 X 160 --> ..

def quick_sort(data):
    """快速排序"""
    length = len(data)
    # print(length//2)
    if length >= 2:  # 递归入口及出口
        mid = data[length // 2]  # 选取基准值,也可以选取第一个或最后一个元素
        print(mid)
        left, right = [], []  # 定义基准值左右两侧的列表
        data.remove(mid)  # 从原始数组中移除基准值
        for num in data:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return data

if __name__ == '__main__':
    # 示例:
    array = [2, 3, 5, 7, 1, 4, 6, 15, 5, 2, 7, 9, 10, 15, 9, 17, 12]
    print(quick_sort(array))
    # 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

合并排序

将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
public static void mergeSort(int[]array){

  int length=array.length;
  int middle=length/2;

  if(length>1){
    int[]left=Arrays.copyOfRange(array,0,middle);//拷贝数组array的左半部分
    int[]right=Arrays.copyOfRange(array,middle,length);//拷贝数组array的右半部分
    mergeSort(left);//递归array的左半部分
    mergeSort(right);//递归array的右半部分
    merge(array,left,right);//数组左半部分、右半部分合并到Array
  }
}

//合并数组,升序
private static void merge(int[]result,int[]left,int[]right){

  int i=0,l=0,r=0;

  while(l<left.length&&r<right.length){
    if(left[l]<right[r]){
      result[i]=left[l];
      i++;
      l++;
    }else{
      result[i]=right[r];
      i++;
      r++;
   }
  }

  while(r<right.length){//如果右边剩下合并右边的
    result[i]=right[r];
    r++;
    i++;
  }

  while(l<left.length){
    result[i]=left[l];
    l++;
    i++;
  }
}

深度优先搜索

​ 树(由上到下) —> 栈结构遍历

广度优先搜索

用图的查找算法,主要解决两类问题:

  <1.从节点A出发,有前往节点B的路径吗?
  <2.从节点A出发,前往节点B的哪条路径最短?(段数/边最少的路径)

实例:在人际圈中查找水果经销商 –你的人际圈(一度关系)、你朋友的人际圈(二度关系)、朋友的朋友的人际圈(三度关系)

狄克斯特拉

找出最快到达目的地的路径。(所用时间最少的路径)

区别广度优先搜索:找出段数最少的路径(尽量少转车而达到目的地的路径)

狄克斯特拉算法用于每条边都有关联数字的图,这些数字称为权重(weight)。

带权重的图称为加权图(weighted graph),不带权重的图称为非加权图(unweighted graph)。


**负权边** 时,该算法不使用,可采用[贝尔曼-福德算法(Bellman-Fordalgorithm)]

实例: 换钢琴

总结:

  要计算非加权图中的最短路径,可使用广度优先搜索。
  要计算加权图中的最短路径,可使用狄克斯特拉算法(只适应有向无环图)。

贪婪算法

选择每个最优,则全最优。(排课表、背包问题、集合覆盖问题、近似完全问题)   近似算法(NP完全问题)

这是一种近似最优的算法(背包问题:最多拿10千克重的物品,请选择价值最大的。 10kg 6000元的音响、4kg 5000元的笔记本电脑、6kg 2000元的手提琴,通过贪婪算法,结果会选出10kg 6000元的音响,而 后面两者之后大于6000元的音响的价值。)

动态规划

将问题分成各个小问题,先解决小问题,再逐步解决大问题。
(背包问题、最长公共子串)

K最近邻算法

1.创建推荐系统(特征抽取、回归<期望值>、挑选合适的特征)
2.机器学习(OCR<图像识别文字>、创建垃圾邮件过滤器<贝叶斯分类器>、股票市场预测<影响因数多>)

总结/扩展

1.二叉树
2.反向索引
3.傅里叶变换(分类、DNA分析、音乐识别)
4.并行计算
5.MapReduce
	<1.分布式算法
	<2.映射函数
	<3.归并函数
6.布隆过滤器和HyperLogLog
7.SHA算法
8.局部敏感的散列算法
9.Diffie-Hellman密钥交换
10.线性规划

参考

«算法图解»

  • ”程序员小灰“ 公众号 (推荐)

合并排序

贝尔曼-福德算法(Bellman-Fordalgorithm)

算法示例

二分法查找-百度百科

快速排序-百度百科

K最近邻算法

深度/广度优先搜索


欢迎拍砖,多多交流,转载请注明出处:[没长正的技术专栏](http://blog.meizhangzheng.com) 如涉及侵权问题,请发送邮件到xsj34567@163.com,如情况属实本人将会尽快删除。


上一篇 常用集合-Map

下一篇 常用集合-List

Comments

Content