背景

最近总结下来想写一系列文章的专栏，先从算法导论入手， 巩固下基础知识体系，避免大脑秀逗。计划大概半年多时间抽炼出常见内容的系列大纲笔记，供记录和学习， 如有需要指正地方望邮件交流。

leecode 算法题目主要也是锻炼思考

1
print 'life and world'

简明摘要

一、基础部分

1.NP完全理论

  • P：所有可以在多项式时间内求解的判定问题构成P类问题
  • NP：所有的非确定性多项式时间可解的判定问题构成NP类问题
  • NPC：NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)
    2.递归式
    给出了递归式推导的三种方法
  • 代换法：数学归纳，根据规律推测出递归式
  • 递归树：分治时间复杂度的尤其适合递归树推算
  • 主定理公式：定理4.1(主定理) 令a≥1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式 T(n) = aT(n/b) + f(n)
    3.概率分析与随机算法
  • 随机算法，不依赖输入，输出和输入无关

二、排序算法与顺序统计

1.堆排序

  • 堆：完全二叉树
  • 大根堆，ASC排序
    2.快排序
  • piovit 枢纽元素x，p r对x比较 。回归x到正确位置。对左边的QS；对右边QS
    3.线性时间排序
  • 计数，确定数x在第几个位置
  • 基数，0~9依次排序。 稳定
  • 桶排序，均匀分布的放在排序号的桶，对桶中元素进行排序
    4.中位数与顺序统计学

三、数据结构

1.栈与队列

  • 特性
  • 可以相互转化
    2.链表
  • 单向链表；表头；表尾
  • 双向链表、带哨兵的环形双向链表（哑对象dummy）
    3.散列表
  • 散列函数：除法、乘法、全域散列
  • 链表法、开放地址法（双重散列）
  • 简单一致散列假设
    4.二叉查找树
  • 节点x， x左子树最大不超过x；x右子树最小不小于x
  • 节点x：value，left、right、parent
    5.红黑树
  • 二叉查找树、平衡特性
  • 根节点 黑色；节点或红或黑；叶子节点黑色（nil节点也称哨兵节点）
  • 红节点的两个儿子都是黑节点
  • 每个节点开始，到其子孙节点的所有路径上包含的黑节点个数相同

四、高级设计
1.动态规划
2.贪心算法
3.平摊分析

五、高级数据结构
1.B树：

六、图算法
1.图基本算法
2.最短路径、最小生成

七、算法研究
1.数论相关算法
2.字符串匹配

版权声明：本文为博主原创文章，未经允许不得转载。