算法分析与设计

chapter①：算法引论

定义：解决某种问题的方法

特征：输入，输出，确定性（指令清晰无歧义），有限性（指令执行次数有限）

算法复杂性の分析

  • 时间复杂性：T=T(N[问题规模],I[算法的输入],A[算法本身])

  • 空间复杂性 ：S=S(N,I)

渐进时间复杂性＝时间复杂度

大O表示法（算法时间运行时间的上界）

  • 设f(n)和g(n)是定义在正整数集上的正函数，若有正常数C和自然数n0。使得当n≥n0时，有f(n)≤C(g(n))，则称f(n)=O(g(n))，也称f(n)的阶不高于g(n)的阶

大Ω表示法（算法时间运行时间的下界）

  • 设f(n)和g(n)是定义在正整数集上的正函数，若有正常数C和自然数n0。使得当n≥n0时，有f(n)≥C(g(n))，则称f(n)=Ω(g(n))，也称f(n)的阶不低于g(n)的阶

θ表示法（算法时间运行时间的准确界）

  • C1(g1(n))≤f(n)≤C2(g2(n))

chapter②：递归与分治策略

神魔是递归？

)

还是……

从上面的两张图我们可以看出，递归就是自己调用自己的过程。在算法中就是算法自己调用自己，这就是递归算法

很容易知道函数中自身调用自己就成为递归函数

分治（divide&conquer）是乜嘢？

凡治众如治寡，分数是也。分治分治，分而治之。大白话就是说把一个规模很大的问题分解成一个个规模较小的子问题，逐个求解，然后子问题的解再“治理”成大问题的最终解

如何使用分治法解决问题？

  1. 解决小规模的问题
  2. 分解问题（divide）
  3. 递归求解子问题
  4. 将所有子问题的解合并为主问题的解

分治?=递归

分治是解决问题的一种思想，递归是解决问题的一种方法，也就是说用分治法解决问题的具体实现形式大多是采用递归的方法

有关递归的经典算法实例：

汉诺塔问题（略）

整数划分问题

问题定义：一个非负正整数都能拆分成若干个数之和或者恰好为自身，比如6这个整数。可以被划分为

6
5+1
4+2 4+1+1
3+3 3+2+1 3+1+1+1
2+2+2 2+2+1+1 2+1+1+1+1
1+1+1+1+1+1

一共有11种划分。并且我们注意到最大的加数是它本身。所以这称为6的划分。如果我们想要得到最大加数≯m的划分个数。比如我们想要最大加数≯5的划分个数，通过上面的表格可以很容易地知道个数是9个，我们用一个函数来表示这个关系f(n,m)

  1. 我们很容易知道当n=1时，也就是——————f(1,m)，因为1的划分只能是1，什么你说1+0+0+0+0…不行么，我劝你还是关闭网页吧（bushi）

  2. m=1时，——————f(n,1)，也就是说n=(1+1+…+1)[n个1]

  3. 当n=m时，从上面的表格可以知道，f(n,n)=1+f(n,n-1)，”1“指的是加数是整数本身时的划分个数，而f(n,n-1)则指的是不包括整数本身的划分个数

  4. 当n>m>1时，f(n,m)：

    • 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);
  • 当划分中包含m时，{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m。此时的划分个数其实就是n-m的划分个数，也就是f(n-m,m)
    • 所以f(n,m)=f(n,m-1)+f(n-m,m)
赏