数据结构与算法分析-笔记

Chapter 1 Data Structures and Algorithms

1.4 Problems, Alogorithms, and Programs

Q:What can be called an algorithm?
1.It must be correct.
2.It is composed of a series of concrete steps.
3.It is no ambiguity.
4.It must be composed of a finite number of steps.
5.It must terminate.

Chapter 2 Mathematical Preliminaries

2.3 Logarithms 对数

若${\log }_{2}x=y$，则2可省略：$\log x=y$。

Chapter 3 Algorithm Analysis*

Asymptotic analysis attempts to estimate the resource consumption of an algorithm.

3.1 Introduction

growth rate
2 < ${\log }_{2}x$ < $n^{2/3}$ < n < $n^2$ < $3^n$ < n!

3.4 Asymptotic Analysis 渐近分析

Upper Bounds 上限：$O\left(g(n)\right)$
Lower Bounds 下限：$\Omega \left(g(n)\right)$
当上限下限一样时用：$\Theta \left(g(n)\right)$

Simplifying Rules 化简法则
1.省略常系数：$\Theta \left(kg(n)\right)=\Theta ($