算法

• 算法的分类

  • 决定性算法：对于给定的输入只有一种方式能确定下一步采取的操作，如求一个集合的合只需要逐个相加并不需要进行猜测。
    非决定性算法：非决定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。如查找算法会先猜测数组中某个数，再验证其是否是需要查找的那个数。

• 需要解决的判定问题的分类

  • P问题：能够用决定性算法在多项式时间内解决的问题。
  • NP问题：能够用非决定性算法在多项式时间内解决的问题。
  • NPC问题：这里P类问题一定属于NP类问题。如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题，该问题则成为NP完整性，也成为NPC问题。

• 算法的复杂度

  • O表示法 表最小上界
  • Ω表示法 表最大下界
  • Θ表示法 当最小上界和最大下界相等时

刷题顺序

• 第一遍按照tag刷，第二遍一题多解，多题同解

心得

• 先看是否有现成的工具类可以解决
• 主要判断边界条件
• 如何找到最优解
  • 从数据状况出发
  • 从要求的时间复杂度出发

对数器

• 1.有一个你想要测的方法a；
• 2.实现一个绝对正确但是复杂度不好的方法b；
• 3.实现一个随机样本产生器；
• 4.实现对比算法a和b的方法；
• 5.把方法a和方法b比对多次来验证方法a是否正确；
• 6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
• 7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

递归

• Master公式
  $$
  T[N] = aT[\frac{N}{b}]+O(N^d)
  $$

  • 变量解释

    • b:子过程的样本量
    • a:子过程的计算次数
    • O(N^d):子结果合并的时间复杂度

  • 当d<$log_ba$时，时间复杂度为O($N^{log_b,a}$)

  • 当d=$log_ba$时，时间复杂度为O(($N^d$)*logN)

  • 当d>$log_ba$时，时间复杂度为O($N^d$)

  • 如果a的x次方等于N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作x=log(a,N)