算法与数据结构系列 ( 一 ) - 算法的级别区分理解

算法的级别

?

O(1)、O(n)、O(n^2)、O(log n)、O(n log n)这些都是算法时间空间复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。O 后面的括号中有一个函数，指明某个算法的耗时 / 耗空间与数据增长量之间的关系。其中的 n 代表输入数据的量

O (1) 的理解

• O(1)?就是最低的时空复杂度了，也就是耗时 / 耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时 / 耗空间都不变。无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
• 举个栗子
• 比如你将家里的衣服很多，装了十个箱子，分别给他们打上标记?1?-10。有一天，你突然想穿?10?号箱子的一件衣服。你就可以迅速打开箱子把衣服拿出来，而且速度非常快。

O (n) 的理解

• 时间复杂度为 O(n) ，就代表数据量增大几倍，耗时也增大几倍。
• 很多常见的遍历算法，要找到一个数组里面最大的一个数，你要把整个数组都 for 一次，操作次数为 n，那么算法复杂度是 O(n)
• 又举个了栗子
• 有一天你突然很想穿某一件衣服，但是忘记衣服放在那个箱子里面了。你就需要从 10 个箱子里面挨个翻出来，并且找到你想要穿的衣服。

O (n^2) 的理解

• 时间复杂度 O(n^2)，就代表数据量增大 n 倍时，耗时增大 n 的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的 O(n^2) 的算法，对 n 个数排序，需要扫描 n×n 次。
• 用冒泡排序排一个数组，对于 n 个变量的数组，需要交换变量位置次，那么算法复杂度就是 O().
• 双举个了栗子
• 因为你看了我的博客，觉得衣服乱放有点不好，所以你把衣服，裤子，分别放在特定的箱子里面。
• 当你想穿某件衣服的时候，只需要找到那个存放衣服的箱子，并且从箱子里面的衣服里面找到你想穿的哪一件就好了

O (log n) 的理解

• 当数据增大 n 倍时，耗时增大 log n 倍（这里的 log 是以 2 为底的，当数据增大 256 倍时，耗时只增大 8 倍，是比线性还要低的时间复杂度）。二分查找就是 O(log n) 的算法，每找一次排除一半的可能，256 个数据中查找只要找 8 次就可以找到目标。这种查找的方法的复杂度就是 O(log n)
• 叒举个了栗子
• 某一天，你忘记了钱包不知道放哪里了（在 6 号箱子），但是被你收入箱子里面了。但是箱子太多，你找了朋友帮忙找。然后你安排你的朋友一人负责找一个箱子，并且他们找的时候，还会问你是不是这个，直到 6 号朋友找到了钱包

O (n log n) 的理解

• 同理，O(n log n)?就是?n?乘以?log n，当数据增大?256?倍时，耗时增大?256 * 8 = 2048?倍。而且这个复杂度高于线性低于平方

?

本系列文章，基本写的是 O (n^2) 级别的。

?

• 众所周知，O(n^2) 的排序算法是比较基础的 (很多时候都用不上),那我们为什么还要去学习 O(n^2) 这种级别的算法呢？

可能在我看来，无非就是以下几点。

• 基础 - 大家也不要小瞧基础算法，很多基础算法的思路是非常好的。
• 简单 - 编码简单，易于实现。简单的排序算法思想会衍生出复杂的排序算法
• 有效 - 在某些特殊情形下，O(n^2) 会比 O(log n) 或者 O(n log n)，更加简单有效

更多学习内容请访问：

腾讯T3-T4标准精品PHP架构师教程目录大全，只要你看完保证薪资上升一个台阶（持续更新）

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!