1

【算法基础】导引

 2 years ago
source link: https://www.guofei.site/2017/05/18/algorithm0.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

【算法基础】导引

2017年05月18日

Author: Guofei

文章归类: 8-数据结构与算法 ，文章编号: 500

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2017/05/18/algorithm0.html

Edit

复杂度

一些定义：

定义1

O(g)O(g)代表一组函数，
f∈O(g)⇔f∈O(g)⇔
∃n0,c∃n0,c使得∀n≥n0,f(n)≤cg(n)∀n≥n0,f(n)≤cg(n)

定义2

Ω(g)Ω(g)的定义恰恰相反
∃n0,c∃n0,c使得∀n≥n0,f(n)≥cg(n)∀n≥n0,f(n)≥cg(n)

定义3

Θ(g)=O(g)∩Ω(g)Θ(g)=O(g)∩Ω(g)

递归中复杂度主定理

如果递归计算量是这样的：
T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n) 那么，复杂度为：
Θ(nlogba)Θ(nlogba)

知识目录

基本数据结构

  • 链表
    • 单循环链表
    • 双向循环链表

堆栈、队列

  • stack
  • queue
  • 优先队列、优先堆
  • 多级反馈队列
  • 二叉树：以及各种遍历算法
  • 哈夫曼树与编码
  • B树与B+树

基本算法

  • DFS/BFS
    • 遍历（借助queue做BFS，借助stack做DFS）
您的支持将鼓励我继续创作！

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK