算法数学基础 - 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完全理论

阅读更多

Trie字典树

一、字典树

字典树——Trie树,又称为前缀树(Prefix Tree)、单词查找树或键树,是一种多叉树结构。

上图是一棵__Trie__树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:

  1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

  2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

  3. 每个节点的所有子节点包含的字符互不相同。

    • 通常在实现的时候,会在结点结构中设置一个标志,用来标记该节点处是否构成一个单词(关键字)。
    • 可以看出,Trie树的关键字一般都是字符串,而且Trie树把每个关键字保存在一条路径上,而不是一个节点中。另外,有两个公共前缀的关键字,在Trie树种前缀部分的路径相同。所以Trie又称为前缀树。
阅读更多