算法学习笔记

Posted on

从30号开始看起一些常用的算法和思想，有所裨益，把要点记录在博客上，不定期更新。

  1. 主定理

    设有递推关系式
    情形1. 若存在常数$$\epsilon$$有$$f(n)=O(n^{log_b(a)-\epsilon})$$，则
    情形2. 若$$k\ge0$$且
    则
    情形3. 若存在$$\epsilon>0$$有同时存在$$c<1$$满足
    则

  1. 大整数乘法
    $$c=(a_1*b_1)10^n+(a_1b_0+a_0b_1)10^{n/2}+a_0b_0$$
    计算次数$$M(n)=3M(n/2)$$
    即$$M(n)=3^{log_2n}=n^{log_2 3}$$
    类似地，用分治解矩阵乘法（减少乘法运算次数到7次）

  2. 最近点对问题
    d=min{左边，右边}
    对分界线[x-d,x]区域内的每个点P0，和右边区域[x,x+d]内所有点P计算距离
    优化点：
    P和P0的y值只能相距d
    P0只需计算和他最近的6个点，具体图在网上有。实际上只需高于P0的4个点，因为排序不用和后面的比，有重复

  3. 凸包问题
    问题：找包含点集的凸多边形，面积最小
    解决：快包
    要点：点集的水平最左点，水平最右点，竖直最高点，竖直最低点都一定是多边形的顶点，然后递归。

  4. 整数划分
    元素可相同的情况，递减地递归 参数有(n剩余数, k第几次划分, last上一次划分的结果)
    对互不相同的情况，除了递归还可以递推求方案数 f(n, k) = f(n-1, k-1) + f(n-k, k)
    第一项，如果单独划一个1出来；第二项，如果不划1，相当于所有元素减1再递归

  5. 组合排列
    排列里有一个JohnsonTrotter算法

  6. 带权中位数
    问题：找一个中心，使得其他点一维的位置*权值和最小
    解决：按位置快排，然后权值累加和，恰超过一半权值的位置是最小的
    拓展：多中心，动归
    f(n, p) = min{(i, p-1)+cost[i+1, p]}
    在前i个里建p-1个中心，剩下的花费和归第p个中心算

---以上---