# 数据结构和算法入门

## 如何学习数据结构和算法

- 边学边练，适度刷题
- 多问、多思考、多互动
- 打怪升级学习法
- 知识需要沉淀，不要想试图一下子掌握所有

## 如何分析、统计算法的执行效率和资源消耗

**复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半**。

### 为什么需要复杂度分析？

事后统计法的局限性：

**1. 测试结果非常依赖测试环境**

**2. 测试结果受数据规模的影响很大**

### 时间复杂度分析

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示**代码执行时间随数据规模增长的变化趋势**，所以，也叫作**渐进时间复杂度**（asymptotic time complexity），简称**时间复杂度**。

**1. 只关注循环执行次数最多的一段代码**

**分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了**。

**2. 加法法则：总复杂度等于量级最大的那段代码的复杂度**

**总的时间复杂度就等于量级最大的那段代码的时间复杂度**。

**3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积**

### 几种常见时间复杂度实例分析

![img](http://dunwu.test.upcdn.net/snap/20200605165440.png)

### 空间复杂度分析

时间复杂度的全称是**渐进时间复杂度**，**表示算法的执行时间与数据规模之间的增长关系**。类比一下，空间复杂度全称就是**渐进空间复杂度**（asymptotic space complexity），**表示算法的存储空间与数据规模之间的增长关系**。

## 浅析最好、最坏、平均、均摊时间复杂度

**最好情况时间复杂度**（best case time complexity） - **最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度**。

**最坏情况时间复杂度**（worst case time complexity） - **最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度**。

**平均情况时间复杂度**（average case time complexity）

**均摊时间复杂度**（amortized time complexity）