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

算法的级别

 

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架构师教程目录大全，只要你看完保证薪资上升一个台阶（持续更新）