算法基础
算法分析:
解决问题的途径有很多,意味着有很多的算法可供选择.那么,如何选择以及消耗的时间/性能在不同算法之间.会存在巨大的差异.在了解算法前,应学会如何分析算法.
数据量 n ;(输入规模)
单次执行时间 t(单次循环执行语句消耗时间)
在算法的比较中, t 可以认为全部为1(即单挑语句的执行时间认为一致).
从而获得一个关于输入量n的函数. 根据这个函数,与实际可能出现的n分布情况.
散列表(hash表)
NP 问题 :
可以简述为阶乘组合问题.(最常见,也最难解决)
最短路径:
多地点,多路径,路径有权值.权值为限制最佳条件.(单向路径最佳,双向也可以)
贪婪算法:
对于NP 问题,求取近似的最佳结果的算法.(结果非最佳).
第一步选取权值最大的一项,后面递减.
迪克斯特拉算法:
求解最短路径问题的算法.算法思想是两点之间,直连或借助其他点,每段分路径.取权值最小.加权之后,得出的路径根据权值筛选最佳路径.
目的 是A -> D .其中有路径 A -> D , A -> B -> D ,A -> C -> D
则 求解思路是 求出 A -> B 所有方案的最优解,B -> D 所有方案的最优解. 各个子最优解之和,取最优解.
动态规划
用于解决NP问题的算法.递归求出最小最优解,然后获得最佳最优解.
详情见后续叙述.
最近临近值
根据属性分类,来源新数据与旧类别比较.更为相似的作为同一类.(主要用于智能推送)
广度优先搜索.
多因素,取主因素最快速的算法.(例子:朋友圈经销商查找.)
