算法学习笔记

从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个中心算

和土豪当朋友!
---以上---