算法
- 有穷性,确定性,输入,输出,可行性
- 复杂度分时空复杂度,时间复杂度为
,空间复杂度可以划分为输入所需存储,程序本身存储,逻辑运算所需存储。
- 算法结构有顺序结构,选择结构,循环结构
栈
- 操作插入查询弹出的都是栈顶元素
队列
- 操作的查询弹出都是队头元素
- 插入都是插入到队尾
树
- N个点N-1条边列检的结构
- 一般有一个确定的跟根
- 先中后序遍历指的是根节点的遍历顺序
- 后缀表达式用的是中序遍历
图
- 有向图和无向图以及不连通图或者是连通图之分。
- 度可分入度出度
- 欧拉路有两个奇点,欧拉回路有零个奇点
N,P,C问题
- P问题:指存在多项式时间解法的问题,比如二分查找
- NP问题:指存在多项式时间验证的问题,比如独立集问题
P问题一定是NP的,因为只需要判定给定的解是否等于计算得到的解就可以。 - NPC:指所有的NP问题都可以多项式规约到它的问题