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 类似这种需要手写。
红黑树类似魔方,要根据规则去算。
常用的算法还是要知道,但实际用得不多,但是面试却会问,这个是作为门槛。
是为了检查面试者的思维。
对计算机的认知深度。
总结
算法就是:一堆数据找最优解。
大多数算法不需要手写,但是需要知道原理。
对于架构师应该对算法保持好奇心,需要知道算法的原理,掌握算法的思想,融汇贯通,在架构设计的时候可以触类旁通使用到这些思想,再使用的时候需要了解他们的优缺点,适用场景,以做好应对。
评论