数列求和公式

1. 函数渐近界的定理

   • 定理1

     设$f$和 $g$是定义域为自然数集合的函数：

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

     （2）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=0$，那么$f(n)=o(g(n))$。

     （3）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=+\infty$，那么$f(n)=\omega(g(n))$。

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

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

算法研究的主要内容

1. 计算复杂性理论（Computational complexity theory）

   • 常见问题：

     • 货郎问题 （NP-hard 问题）

     • 0-1背包问题

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

     • 双机调度问题

   • NP-hard问题

     • 问题有数千个，大量存在于各个领域；

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

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

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

   • 程序 = 算法 + 数据结构

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

     • 算法的研究目标：

       问题 → 建模并寻找算法 （算法技术设计）

       算法 → 算法的评价 （算法分析方法）

       算法类 → 问题复杂度的估计 （问题复杂度分析）

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

   • NP完全理论

接着上一篇字典树结构的讲解，我们接着使用C++和Python来实现字典树。

一、LeetCode的字典树

在LeetCode 208 要求实现字典树。

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

一、字典树

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

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

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

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

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

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