贪心算法基础

本文开始记录贪心算法的学习。

贪心算法的例子——活动选择问题

输入:S={1,2,...,n}S=\{1,2,...,n\}nn项活动的集合,sis_ifif_i分别为活动ii的开始和结束时间。

活动iijj相容     sifj\iff s_i \ge f_jsjfis_j \ge f_i

求:最大的两两相容的活动集AA

阅读更多

分治策略-基础.md

基础思想

分治策略(Divide and Conquer)基本思想:

  1. 将原始问题划分或者归结为规模较小的子问题;

  2. 递归或迭代求解每个子问题;

  3. 将子问题的解综合得到原问题的解。

阅读更多

分治策略-算法设计思想.md

算法设计思想

  • 将原问题归结为规模为n-1的2个子问题;

  • 继续归约,将原问题归结为规模为n-2的4个子问题。继续…,当子问题规模为1时,归约过程截止。

  • 从规模1n-1,陆续组合两个子问题的解。直到规模为n

  • 分析方法:递推方程。

阅读更多

分治策略-快速排序.md

基础思想

  • 用首元素xx作划分标准,将输入数组AA划分成不超过xx的元素构成的数组ALA_L,大于xx的元素构成的数组ARA_R。其中,AL,ARA_L,A_R从左到右存放数组AA的位置。

  • 递归地堆子问题ALA_LARA_R进行排序,直到子问题规模为11时停止。

阅读更多

分治策略-幂乘问题.md

幂乘问题

输入:aa为给定实数,nn为自然数

输出:ana^n

传统算法思想

顺序相乘 an=(...(((aa)a)a)...)aa^n=(...(((a\quad a)a)a)...)a

乘法次数:Θ(n)\varTheta (n)

阅读更多

分治策略-改进.md

减少子问题数

依据

分治算法的时间复杂度方程

W(n)=aW(n/b)+d(n)W(n) = aW(n/b) + d(n)

aa:子问题数,n/bn/b:子问题规模,d(n)d(n):划分与综合工作量。

阅读更多

分治策略-典型算法.md

选择问题

选最大和最小

输入:集合LL(含nn个不等的实数)

输出:LL中的第ii小的元素

  • i=1i=1,称为最小元素

  • i=ni=n,称为最大元素

位置处在中间爱你位置的元素,成为中位元素

nn为奇数,中位数唯一,i=(n+1)/2i=(n+1)/2

nn为偶数,可指定为i=n/2+1i=n/2+1

选最大算法:顺序比较,在最坏情况下的时间为W(n)=n1W(n)=n-1

阅读更多

分治策略-卷积

卷积及其应用

向量计算

给定向量:

  • a=(a0,a1,...,an1)a=(a_0, a_1, ..., a_{n-1})

  • b=(b0,b1,...,an1)b=(b_0, b_1, ..., a_{n-1})

向量和: a+b=(a0+b0,a1+b1,...,an1+bn1a+b=(a_0+b_0,a_1+b_1,...,a_{n-1}+b_{n-1}

阅读更多

算法数学基础 - 2

  1. 函数渐近界的定理

    • 定理1

      ffgg是定义域为自然数集合的函数:

      (1)如果limnf(n)/g(n)\lim\limits_{n\rightarrow\infty}f(n)/g(n)存在,并且等于某个常数c>0c>0,那么f(n)=Θ(g(n))f(n)=\Theta(g(n))

      (2)如果limnf(n)/g(n)=0\lim\limits_{n\rightarrow\infty}f(n)/g(n)=0,那么f(n)=o(g(n))f(n)=o(g(n))

      (3)如果limnf(n)/g(n)=+\lim\limits_{n\rightarrow\infty}f(n)/g(n)=+\infty,那么f(n)=ω(g(n))f(n)=\omega(g(n))

      推理1 → 多项式函数的阶低于指数函数的阶nd=o(rn),r>1,d>0n^d=o(r^n),r>1,d>0

      推理2 →对数函数的阶低于幂函数的阶lnn=o(nd),d>0\ln n=o(n^d),d>0

阅读更多

算法数学基础 - 1

算法研究的主要内容


  1. 计算复杂性理论(Computational complexity theory)

    • 常见问题:

      • 货郎问题 (NP-hard 问题)

      • 0-1背包问题

        问题的解为0-1向量 <X1,X2,...,Xn><X_1,X_2,...,Xn_>

      • 双机调度问题

    • NP-hard问题

      • 问题有数千个,大量存在于各个领域;

      • 至今未找到有效算法:现有算法的运行时间是输入规模的指数或更高阶函数;、

      • 至今没有人能够证明对于这类问题存在多项式时间算法;

      • 是否存在多项式时间算法等价于存在有效计算的边界

    • 程序 = 算法 + 数据结构

      • 好的算法: 提高求解问题的效率;节省存储空间

      • 算法的研究目标:

        问题 → 建模并寻找算法 (算法技术设计)

        算法 → 算法的评价 (算法分析方法)

        算法类 → 问题复杂度的估计 (问题复杂度分析)

        问题类 → 能够求解的边界 (计算复杂性理论)

    • NP完全理论

阅读更多