数据结构的结构复杂度你了解么

灰太狼 2024-04-08 08:53 68阅读 0赞

**目录**

一. 数据结构的作用

二. 数据结构的类型

2.1 线性结构

2.2 树

2.3 图

三. 示例理解数据结构

四. 常用数据结构复杂度

五. 数据结构专栏

--------------------

## **一. 数据结构的作用**  ##

>  **数据结构，对应的英文单词是data structure，是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。**

> 数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。

> 不管是物理结构还是逻辑结构，数据结构的某些属性可以被外界所感知，而另外一些属性却是不可见的。换句话说，数据结构包含外部特性和内部结构两个方面。外部特性决定了它将如何被使用，而内部结构决定了它的原理和具体实现。初学数据结构时，可以更多的关注它们的外部特性，在熟练使用并体会到数据结构的好处之后再学习它们的内部结构，并根据其中的设计思想创造出新的数据结构。

--------------------

## 二. 数据结构的类型 ##

### 2.1 线性结构 ###

>  *  数组与链表：单 / 双向链表
>  *  栈与队列
>  *  哈希表
>  *  堆：最大堆 ／ 最小堆

### 2.2 树 ###

>  *  树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。

### 2.3 图 ###

>  *  图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系

> 下图分别为：节点、线性结构、树形结构、图形结构

![72a4b7872319eff8df5275efd552f27c.png][]

--------------------

## 三. 示例理解数据结构 ##

> 有一只自动储钱罐，它有一个孔和一个按钮。存钱的时候，你可以从小孔往里面投一枚硬币；取钱的时候，只要按一下按钮，面值最大的硬币就会从孔里掉出来。

![f6c9c8ca19d6918cd94697acb0590d2e.jpeg][]

> 自动储钱罐的设计者告诉你：钱罐里有一个很小的机器人，每次按下按钮的时候，它就从钱罐里找出最值钱的一枚，从孔里扔出来。如果硬币有很多的话，从一大堆钱里找到最值钱的硬币是需要花时间的，所以可能你按下按钮以后需要等待几分钟，让小机器人慢慢找。

>  **小机器人如何工作：组织投入的硬币，和拿取最值钱的硬币过程，是我们需要设计的。**

> 例如小机器人可以这样工作：当你扔一枚硬币进来的时候，它什么都不做，自己睡大觉；当你按按钮的时候，它慌了，赶紧找钱。它先随便挑出一个硬币拿在手里，然后把其他所有硬币的看一遍，如果发现更值钱的，就用把手里的硬币换掉，最后手里拿着的就是最值钱的硬币，然后从孔里扔出去。

> 下面是小机器人的语言实现程序（仅作为示例）：

public void new_coin (){
 	zzzZZZ ();
 }
 public void delete_max (){
 int best = 0;
 for(int i = 1; i < coin_count ; i ++){
 if( coin [i] > coin [ best ]) {
 best = i;
 }
 }
 throw_away ( best );
 }

> 其中coin\[i\]表示第i枚硬币，throw away(i)表示把第i枚硬币扔出去且终止程序。best代表当前手中的硬币，它在小机器人已经检查过的硬币中是面值最大的。由于coin是无序数组，我们把这种方法称为无序数组实现法。

> 可以预料，这个钱罐\\添加硬币"很快（小机器人啥都不做），找最大面值却很慢。如果小机器人检查一枚硬币的时间是0.01秒，那么有100个硬币时需要1秒，有10,000个硬币时需要100秒（ 约两分钟） ， 而1,000,000个硬币时就需要10,000秒（约2.8小时）！你可以忍受这样的速度吗？

> 如果改改小机器人的程序，情况就完全不一样了！如果你曾留意过超市里的售货员是怎样找零钱的，你也立刻明白这个方案：
> 
>  *  拿几个不同的小桶，每个桶装一种面值的硬币。
>  *  假设一共有1元、5角、1角、5分、2分和1分共6种面值的硬币，则只需要六个桶。
>  *  当来了一枚新硬币时，小机器人把它放到相应的盒子中；
>  *  需要找钱时，小机器人只需要看1元的盒子里有没有硬币，有的话随便拿一个扔出去；
>  *  如果没有的话再看5角的盒子有没有硬币，有的话随便拿一个扔出去

> 不管有多少硬币，只要盒子装得下，总是最多只需要开6次桶即可，即使每开一个桶需要5秒钟，有1,000,000个硬币时最多也只需要半分钟，比刚才的2.8小时快多了。程序如下：

public void new_coin (int value ){
 	count [ value ] = count [ value ]+1;
 }
 public void delete_max (){
 for(int i = 0; i <= 6; i ++){
 	if( count [i] > 0) {
 throw_away (i);
 }
 }
 }

> 其中count\[i\]表示第i种面值的桶里有多少硬币，throw away(i)表示把一枚面值为i的硬币扔出去。每个count\[i\]保存了捅里的硬币数目，我们把这种方法称为桶实现法。

> 这个方法虽然好，但是前提是只有6种面值。如果1分、2分、3分、4分、. . .99元9角8分、99元9角9分、100元整这1万种面值的硬币都有，那就需要1万个盒子。如果扔的1,000,000个硬币的面值全部不同，那么这个新方法就没有任何优势了。

> 讲了这么多，只是想说明一个问题：相同的外特性（自动储钱罐）可以用多种结构（小机器人的程序）实现，它们的时间效率可能不同，空间开销也可能不同（新程序需要用附加盒子）。事实上，存在一个更好的结构来实现这个储钱罐，它就是数据结构中的**堆**实现法。不管面值有多少种，在有1,000,000个硬币的情况下也最多只需要不到一秒钟。

--------------------

## 四. 常用数据结构复杂度 ##

<table> 
 <tbody> 
 <tr> 
 <td> 数据结构 </td> 
 <td colspan="8"> 时间复杂度 </td> 
 <td> 空间复杂度 </td> 
 </tr> 
 <tr> 
 <td></td> 
 <td> 平均 </td> 
 <td colspan="4"> 最好 </td> 
 <td colspan="4"> 最差 </td> 
 </tr> 
 <tr> 
 <td></td> 
 <td> 访问 </td> 
 <td> 搜索 </td> 
 <td> 插入 </td> 
 <td> 删除 </td> 
 <td> 访问 </td> 
 <td> 搜索 </td> 
 <td> 插入 </td> 
 <td> 删除 </td> 
 <td></td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Array_data_structure" title="数组" rel="nofollow">数组</a> </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29" title="堆栈" rel="nofollow">堆栈</a> </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29" title="队列" rel="nofollow">队列</a> </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists" title="单向链表" rel="nofollow">单向链表</a> </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Doubly_linked_list" title="双向链表" rel="nofollow">双向链表</a> </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Skip_list" title="跳跃表" rel="nofollow">跳跃表</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n log(n)) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Hash_table" title="哈希表" rel="nofollow">哈希表</a> </td> 
 <td> N/A </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> N/A </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Binary_search_tree" title="二叉搜索树" rel="nofollow">二叉搜索树</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Cartesian_tree" title="笛卡尔树" rel="nofollow">笛卡尔树</a> </td> 
 <td> N/A </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> N/A </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/B_tree" title="B树" rel="nofollow">B树</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Red-black_tree" title="红黑树" rel="nofollow">红黑树</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/Splay_tree" title="伸展树" rel="nofollow">伸展树</a> </td> 
 <td> N/A </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> N/A </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/AVL_tree" title="AVL树" rel="nofollow">AVL树</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 </tr> 
 <tr> 
 <td> <a href="https://en.wikipedia.org/wiki/K-d_tree" title="KD树" rel="nofollow">KD树</a> </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> Θ(1) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 <td> O(n) </td> 
 </tr> 
 </tbody> 
</table>

--------------------

## 五. 数据结构专栏 ##

[https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482![icon-default.png_t_M666][]https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482][https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]

[72a4b7872319eff8df5275efd552f27c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0ee990a4142d4d0dbef0d1ee27c26892.png
[f6c9c8ca19d6918cd94697acb0590d2e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/32749ee8f84b48cba2407fad27be5d0e.jpeg
[icon-default.png_t_M666]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3059cfc99402402aa1466e4b4697fee6.png
[https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/weixin_53919192/category_11908333.html?spm=1001.2014.3001.5482