work-08- 算法学习心得

用户头像
蒜泥精英
关注
发布于: 2020 年 07 月 29 日
work-08-算法学习心得

时间复杂度 空间复杂度

P问题:

NP问题:



各类数据结构

数组:

连续,每个单位的长度固定,可直接根据下标算出地址。

O(1)



链表:

O(n)

链表增删数据要比数组性能好得多;

数组链表结合,可以快速查找和快速增删;



HASH表

查询O(1)

增、改O(1)

HASH的本质就是数组;

(1)根据KEY算出HASHCODE;

(2)然后计算HASHCODE对应的HASH表索引;

101%8=5

8是数组的长度;



真实的情况,HASH内放的是指针

可能存在的问题,两个KEY 算出了 同一个 下标,也是有可能,会出现HASH冲突;

此时,解决办法就是指针后指向一个链表,将冲突的KV放到这个链表内;



线程调用栈

函数有个栈帧,所有的局部变量放到栈帧内;

F方法放入栈帧,然后后面的G方法放入栈帧;

栈顶一定是当前的函数;



队列

用队列搜索好友中关系最近的有钱人;

(1)我线入队列;

(2)我处队列,同时找到好友入队列;

(3)好友处队列,然后找好友是否有好友,如有就入队列;

即,每次检查当前出队列的是否有钱人,然后把他的好友入队列;

如果是有钱人,肯定是离你最近的一个有钱人;

(需要注意:需要去重)

用队列搜索最短路径;



二叉排序树

左子树的所有节点的值均小于或等于它的根节点值;

右子树上所有节点的值均大于或等于它的根节点的额值



不平衡二叉排序树

实际使用是平衡的排序二叉树;

左右子树的深度只差绝对值不超过1



左边添加节点,右旋转二叉树恢复平衡

右边添加节点,左旋转二叉树恢复平衡



红黑排序树

作用:是为了保持二叉树的平衡的

如何染色、怎么旋转是写死的(不需要死记),

最多3次就能红黑平衡。



跳表:

跳表类似二分查找,适用于区间查询;



常用算法

穷举算法

递归算法:在方法开始,一定要有个退出函数;否则栈会溢出;

贪心算法:小偷背个背包去偷东西,将哪些商品放进去才能收益最大化



改进贪心算法:

迪杰斯特拉算法(最快路径)

先找到每个节点的最短路径



贪心算法其实不能得到最优解;



动态规划算法解决背包问题:

建立网格二维或多维表格

背包只要二维就可以了



遗传算法也可以解决背包问题

基因编码与染色体

基因组合:染色体

这样的组合有 2^n次方;



适应函数与控制参数;

选择适应度函数: 求和,商品的总价值

选择控制参数:这里为重量,不能超过这个重量;



选择算法:

交叉:

变异



遗传算法得到的不是最优解,但是为较优解。



一致性HASH 类似这种需要手写。

红黑树类似魔方,要根据规则去算。

常用的算法还是要知道,但实际用得不多,但是面试却会问,这个是作为门槛。

是为了检查面试者的思维。

对计算机的认知深度。



总结



算法就是:一堆数据找最优解。

大多数算法不需要手写,但是需要知道原理。

对于架构师应该对算法保持好奇心,需要知道算法的原理,掌握算法的思想,融汇贯通,在架构设计的时候可以触类旁通使用到这些思想,再使用的时候需要了解他们的优缺点,适用场景,以做好应对。



用户头像

蒜泥精英

关注

还未添加个人签名 2018.09.19 加入

还未添加个人简介

评论

发布
暂无评论
work-08-算法学习心得