01_数据结构与算法介绍

ゞ浴缸里的玫瑰 2022-09-10 08:29 155阅读 0赞

## 一、数据结构介绍 ##

#### 1.什么是数据结构 ####

数据结构(datastructure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（百度百科）  
一句话解释：**存数据的，而且是在内存中存！**

#### 2.常见的数据结构 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]

## 二、算法介绍 ##

#### 1.什么是算法 ####

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

一句话描述：**算法是一种解决特定问题的思路**

比如：LRU算法，最近最少使用，解决的就是当空间不够用时，应该淘汰谁的问题，这是一种策略，不是唯一的答案，所以算法无对错，只有好和不好。

#### 2.常见算法 ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 三、算法复杂度介绍 ##

数据结构和算法本质上是”快“和"省"。所以代码的执行效率是非常重要的度量. 我们采用**时间复杂度**和**空间复杂度**来计算

#### 1.时间复杂度 ####

**大O复杂度表示法**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
上例中T(n)=O(n\*n)，也就是代码执行时间随着数据规模的增加而平方增长.  
即：上例中的时间复杂度为**O**( n2)  
时间复杂度也成为**渐进时间复杂度**。  
**计算时间复杂度的技巧**

*  计算循环执行次数最多的代码
 *  总复杂度=量级最大的复杂度

比如把上面两段代码合在一起  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
时间复杂度为**O**( n2)  
嵌套代码的复杂度等于嵌套**内外**代码复杂度的乘积(乘法法则)  
**常见的时间复杂度**

*  **O(1)**  
    这种是最简单的，也是最好理解的，就是常量级  
    不是只执行了一行代码，只要代码的执行不随着数据规模(n)的增加而增加，就是常量级  
    在实际应用中，通常使用冗余字段存储来将O(n)变成O(1)，比如Redis中有很多这样的操作用来提升访问性能  
    比如:SDS、字典、跳跃表等
 *  **O(logn)、O(nlogn)**  
    ![在这里插入图片描述][3262c36a6d36407a8e2686fbbe111ae5.png]  
    2 =n  
    x=log n  
    忽略系数为logn  
    T(n)=O(logn）  
    如果将该代码执行n遍  
    则时间复杂度记录为:T(n)=O(n\*logn），即O(nlogn)  
    快速排序、归并排序的时间复杂度都是O(nlogn)
 *  **O(n)**  
    很多线性表的操作都是O(n),这也是最常见的一个时间复杂度  
    比如：数组的插入删除、链表的遍历等
 *  **O(m+n)**  
    代码的时间复杂度由两个数据的规模来决定  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
    m和n是代码的两个数据规模，而且不能确定谁更大，此时代码的复杂度为两段时间复杂度之和，  
    即  
    T(n)=O(m+n)，记作：O(m+n)
 *  **O(m\*n)**  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
    根据乘法法则代码的复杂度为两段时间复杂度之积，即  
    T(n)=O(m*n)，记作：O(m*n)  
    当m==n时,为O( )

#### 2.空间复杂度 ####

空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系  
比如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:T(n)=O(2n)，忽略系数。即为：  
O(n)，这是一个非常常见的空间复杂度，比如跳跃表、hashmap的扩容  
此外还有:O(1)，比如原地排序、O(n ) 此种占用空间过大  
由于现在硬件相对比较便宜，所以在开发中常常会利用空间来换时间，比如缓存技术  
典型的数据结构中空间换时间是：跳跃表  
在实际开发中我们也更关注代码的时间复杂度，而用于执行效率的提升

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/faf935fe34d9497d8ebb60443dab4c80.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/ff5248d6d6d3470ebbdb421c46a3b042.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/2f4e11d8ce9b40efa6fadf90b5c3ff82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/e5affa6821c24195b13007dd47fd03a7.png
[3262c36a6d36407a8e2686fbbe111ae5.png]: /images/20220829/5fcd8a8d7abe4394a899a425880095e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/55e2543fba0f4e3faff0ed158a390a80.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qC85a2Q6KGrMTEx_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/8c75d86366fe49a8aae5cbc4ce16c241.png