## Basic Definition and Application

• 有向图与无向图
• 图的表示
• 邻接矩阵
• 查看二点间是否有边很方便， $\Theta(1)$
• 遍历复杂度较高, $\Theta(n^2)$
• 邻接表
• 利于稀疏图
• 遍历复杂度 $\Theta(m+n)$， m个结点，n条边
• 检查(u,v)是否为边， O(deg(u))，检查与u相邻的边

## 算法设计与分析笔记0x00 —— 课程介绍及基础知识

computational tractability: 计算的可追踪性，即可用数学语言进行推理证明

## Notation Properties

• If f = O(h) and g = O(h) then f + g = O(h).
• If f = Ω(h) and g = Ω(h) then f + g = Ω(h).
• If f = Θ(h) and g = O(h) then f + g = Θ(h).

focus on speed

## 时间复杂度

• Time complexiy of algorithm is number of steps it takes before it terminates.
• 在算法终止之前操作的步数
• Issue 1: Number of steps depends on input size
• Analyze complexity as a function of input size
• Issue 2: Even for a fixed size, the running time can vary
• Consider worst case
• Sometimes we consider average case
• but we don’t know how the input are distributed
• Issue 3: What counts as a step?
• Eg: check for a word. Step is checking one word or a page.
• we need to user a coarse-grained model, ignore minor details and focus on big picture.
• 此处粗粒度模型，可简单理解为将复杂系统简化

## 算法基础笔记0x00 —— 基本概念和基础数学

• Course structure
• Intro and math review
• Analysis of algorithms
• Sorting
• Search
• Divide and conquer
• Greedy algorithms
• Graphs
• Dynamic programming
• NP
• String algorithms