数据结构-复杂度（一）

目录

一、什么是复杂度？

算法效率：

复杂度：

二、复杂度分类

一、时间复杂度

二、空间复杂度（Space Complexity）

---

了解数据结构之前需要了解复杂度。

一、什么是复杂度？

在介绍复杂度之前我们现分享一个名词叫算法效率。

算法效率：

算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。

算法效率也分为两种： 一种是时间效率，一种是空间效率，也被称为时间复杂度和空间复杂度。

当我们碰到一个问题，并且拥有许多解决这个问题的算法时，我们就会想应该选择哪一种算法合适，要想比较各个算法的好坏，我们就要用到数据结构的复杂度内容来判断，通过复杂度我们可以做到不用计算机实际运行算法来预估算法的性能，而是通过分析算法的复杂度来预估算法的性能。

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

复杂度：

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

在计算 机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

二、复杂度分类

一、时间复杂度

是指执行当前算法所消耗的时间，通常用【时间复杂度】来描述。

时间复杂度不是用计算程序具体耗时来表达的。

常见时间复杂度关系

所消耗的时间从小到大

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

二、空间复杂度（Space Complexity）

是指执行当前算法需要占用多少内存空间，我们通常用【空间复杂度】来描述。

定义：是对一个算法在运行过程中临时占用存储空间大小的量度记做S(n)=O(f(n)).

既然时间复杂度不是用计算程序具体耗时来表达的，

所以同理空间复杂度也不是用来计算程序实际占有的空间。他们只是一个趋势。

数据结构-线性表与链性表（二）_平凡之路无尽路的博客-CSDN博客

参考文献

数据结构—复杂度讲解_好想写博客的博客-CSDN博客

数据结构和时间复杂度简单入门 - 知乎

常见数据结构及复杂度Java实现_淡蓝色_mmm的博客-CSDN博客