数组、链表、二叉树、二叉排序树、红黑树时间复杂度

╰+哭是因爲堅強的太久メ 2023-06-24 15:27 20阅读 0赞

# 查找时间复杂度 #

不论是数组、链表还是二叉树、二叉排序树（搜索树）、红黑树，我们要找到其中特定的一个元素，方法只有一个那就是挨个比较直到找到为止，这就造成了查找的时间复杂度总是与N有关系。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(log<sub>2</sub>N)~O(N)</td> 
   <td>O(log<sub>2</sub>N)</td> 
  </tr> 
 </tbody> 
</table>

*  **数组**：特指无序数组。假设数组中有N个元素，我们要找到其中一个特定的元素，通常要进过N/2次比较，所以时间复杂度上来说还是O(N)。如果数组是有序数组的话，可以折半查找，此时的时间复杂度是O(log2N)。
 *  **链表**：同理于数组，假设有N个元素，要找到其中一个特定的元素，时间复杂度还是O(N)。
 *  **二叉树**：注意是二叉树，父节点与左子节点、右子节点之间没有大小关系，实在不明白，可以看看这篇文章[二叉树（从建树、遍历到存储）Java][Java]。此时要从N个节点中找到特定的节点，只能是遍历每一个元素，时间复杂度是O(N)。
 *  **二叉排序树**：此时父节点与左、右子节点之间就有大小关系了。在理想状态下即节点分布均匀的情况下相当于折半查找，所以时间复杂度是O(log2N)，最坏情况是出现左、右斜树，此时时间复杂度会降到O(N)，一般情况下时间复杂度会介于两者之间即O(N)到O(log2N)。
 *  **红黑树**：虽然红黑树在插入、删除操作上很是麻烦，但是对于查找操作跟二叉排序树是一模一样的，因为红黑树不过是加了平衡算法的二叉排序树而已，二叉排序树最基本的父节点与左、右子节点之间的大小关系肯定是满足的，所以时间复杂度是O(log2N)。

只看表达式的可能感觉不强烈，那我们假设N=1000000（一百万）。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找</td> 
   <td>1000000（一百万）</td> 
   <td>1000000（一百万）</td> 
   <td>1000000（一百万）</td> 
   <td>20~1000000</td> 
   <td>20</td> 
  </tr> 
 </tbody> 
</table>

注意：有人可能会说，二叉排序树这个跨度也太大了吧，直接从二十到一百万，嗯嗯，这也是为什么要用红黑树的原因，想好好理解红黑树的，可以看看这篇文章[关于红黑树，这篇文章你要看啊][Link 1]。

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

# 增加时间复杂度 #

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增加</td> 
   <td>O(1)</td> 
   <td>O(N)</td> 
   <td>O(log<sub>2</sub>N)~O(N)</td> 
   <td>O(log<sub>2</sub>N)</td> 
  </tr> 
 </tbody> 
</table>

*  **数组**： 与数组元素的个数N没有关系，总是存放到下一个空白的存储空间，array\[index\]，之后index++。
 *  **链表**：对于链表要分情况（1）在表头插入，只需要改变几个引用值，所以时间复杂度为O(1)；  
    （2）在指定位置插入一个元素，比如add(int index , E element )。此时增加节点的操作就分为两步，第一步查找，第二步新增，因为查找的时间复杂度是O(N)，新增的时间复杂度是O(1)，所以还是O(N)。
 *  **二叉树排序树**： 新增一个节点需要分为两步，第一步查找（成为谁的子节点？）；第二步新增。  
    新增只需要改变几个引用，时间复杂度是O(1)，主要的时间消耗还是在查找上，所以总的时间复杂度跟二叉排序树的查找一样是要看树节点的分布情况的，一般情况下是O(log2N)~O(N)。
 *  **红黑树**： 同理新增一个节点需要分为两步，第一步查找（成为谁的子节点？）时间复杂度为O(log2N) ；第二步新增，新增过程中为满足平衡而做的颜色变换和旋转所消耗的时间有以下结论（引自经典著作《Java数据结构与算法（第二版）》\[美\]Robert Lafore 著）。

> 插入和删除的时间要增加一个常数因子，因为不得不在下行的路径上和插入点执行颜色变换和旋转。平均起来，一次插入大约需要一次旋转。因此，插入的时间复杂度还是O(log2N) 。

为对比强烈，我们还是以N = 1000000（一百万）为例，感受一下不同数据结构的魅力。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增加</td> 
   <td>1</td> 
   <td>1000000（一百万）</td> 
   <td>20~1000000</td> 
   <td>20</td> 
  </tr> 
 </tbody> 
</table>

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

# 删除时间复杂度 #

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>删除</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>O(log<sub>2</sub>N)~O(N)</td> 
   <td>O(log<sub>2</sub>N)</td> 
  </tr> 
 </tbody> 
</table>

*  **数组**：删除操作也分为两步，第一步找到指定元素，第二步指定元素后的每一个元素前移一位。  
    在元素个数为N的数组中查找指定元素平均需要N/2次比较，时间复杂度为O(N)；将指定元素后的每一个元素前移一位，平均需要移动N/2个元素，时间复杂度为O(N)。总的时间复杂度还是O(N)。
 *  **链表**：删除节点的操作就分为两步，第一步查找，第二步删除。因为查找的时间复杂度是O(N)，删除的时间复杂度是O(1)，所以还是O(N)。
 *  **二叉树**： 删除节点的操作就分为两步，第一步查找，第二步删除。因为二叉树的父节点与左右子节点之间没有大小关系，要查找指定节点只能挨个比较，时间复杂度为O(N)，删除只需要修改一些引用，时间复杂度是常数级的，总的时间消耗O(N)。
 *  **二叉排序树**、**红黑树**： 两者的删除操作都分为两步，一步查找、二步删除。且删除节点的时间复杂度总是常数级的（只用改变几个引用），所以总的时间复杂度就是查找的时间复杂度。

为对比强烈，我们再以N = 1000000（一百万）为例，感受一下这差距。。。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>二叉树</th> 
   <th>二叉排序树</th> 
   <th>红黑树</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>删除</td> 
   <td>1000000（一百万）</td> 
   <td>1000000（一百万）</td> 
   <td>1000000（一百万）</td> 
   <td>20~1000000</td> 
   <td>20</td> 
  </tr> 
 </tbody> 
</table>

[Java]: https://blog.csdn.net/dabusiGin/article/details/102785510
[Link 1]: https://blog.csdn.net/dabusiGin/article/details/104593099