面试常见问题：时间复杂度O是什么？

我们在面试的时候，总有面试官喜欢问，时间复杂度，空间复杂度，就比如像O(n²) 这种，那么这种时间复杂度是怎么定义的，为啥用这种定义的，最后时间复杂度都代表和你程序有什么关系呢？今天也来说说关于复杂度自己的看法。

算法

要说复杂度，那么一定是和你自己的算法有关系的，那么总有人会说，我不知道算法是什么，但是也不耽误我当开发。话是这么说，但是你要考虑一下，这个问题如果在你面试大厂的时候，面试官给他提出的，那你能表示，我虽然不太会，但是我能干活，我估计面试官可能也不太相信你。

工作的时候，只求程序能跑，并不太关注性能，所以尽量避坑（ArrayList Or LinkedList），选择自己擅长会用的就行，但是只要面试到数据结构和算法，必跪无疑。

科班出身的，肯定会对算法有一些概念，因为大学里面可能会学到数据结构和算法，但是如果你只求考试通过，那当我没说。

算法是什么？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用 系统的方法描述解决问题的策略机制。

算法 == 程序的灵魂

算法实际上用通俗的语言说，那就是一种解题的思路，算法，没有对错，但是有好喝不好的区分。

阅读之后会有个更有体系的认识。

常见算法：

就比如我们日常生活中最常见的算法就比如排序中的算法

• 冒泡排序
• 快速排序
• 插入排序
• 归并排序
• 计数排序

还有一些其他的算法，LRU 算法，LFU算法，Hash算法这些，都能实现相同的功能，但是，都没有错，就是看效率的问题，还有就是时间复杂度的问题了。时间复杂度是什么呢？

时间复杂度

大O复杂度表示法

实际上，说得直白点，就是你写的算法，运行的时间，而这个时间在设计上的层面，就可以称之为时间复杂度。

我们假设执行一行代码的时间为t，通过估算，代码的执行时间T(n)与执行次数成正比，记做:

T(n)=O(f(n))

• T(n)：代码执行时间
• n：数据规模
• f(n)：每行代码执行次数总和
• O：代码的执行时间与f(n)表达式成正比

我们来看一个简单的案例

int sum(int n){ int s=0; //t int i=1; //t for(;i<=n;i++){ //t*n s=s+i; //t*n }return s; //t } n=100 1+1+100n+100n+1=200n+2

这样子看下来，我们就可以按照这个公式看到这个时间复杂度，

T(n)=O(2n+2)

但是我们用无限的角度去考了，当n无限大时，低阶、常量、系统都可以忽略，这就等价于：

T(n)=O(n)

这种复杂度就属于，是代码执行时间随着数据规模的增加而增长，也就是数据规模越大，那么需要的代码执行时间就越长，这是其中的一种算法。

几种比较常见的时间复杂度。

O(1) 常量阶

这种表示的意思是，常量级别的时间复杂度，也就是他不会随着数据的增长而增长，而是一个常量值来进行计算的，这种时间复杂度不是不存在，而是相对来说比较少。

O(logn)、O(nlogn) 对数阶(线性)

简单示例如下：

i = 1; while(i <= n){ i = i * 2;// 执行最多 }

而这个时候 x=log₂ n

忽略系数为logn

T(n)=O(logn）

如果将该代码执行n遍，则时间复杂度记录为:

T(n)=O(n*logn），即 O(nlogn)

其实还有很多，就比如

O(nⁿ) n方阶

其实这个属于最好理解的，就比如我们写的嵌套的for循环，就是属于 n方阶，你有多少循环，那就是多少阶

示例代码：

for(x=1; i<=n; x++){ for(i=1; i<=n; i++) { j = i; j++; }}

除此之外，还有

• O(2ⁿ) 指数阶
• O(n!) 阶乘阶

其实看到这个，大家肯定也都感觉出来了，和数学关系很大， 这也是为啥有些公司会要求你的高等数学比较好的原因了。

最好、最坏、平均、均摊时间复杂度

其实这个才是相对来说最难的，因为很多时候，我们理解这个是需要我们从代码层面来理解他的最好，最坏，平均，均摊时间复杂度的。

比如如下的代码：

/** * 找出给定数组中给定元素的位置，如果找不到返回-1 * @param arr 给定数组 * @param target 给定元素 * @return */public int find(int[] arr, int target) { int n = arr.length; for (int i = 0; i < n; i++) { // 依次遍历数组，如果找到和目标元素相同的值，在返回该值所在下标 if (arr[i] == target) { return i; } } return -1;}

1.最好情况时间复杂度：目标元素刚好在数组第一个位置，那么只需要一次就能找到，时间复杂度很明显是常量阶O(1)。

2.最坏情况时间复杂度：目标元素在数组最后一个位置或者不在数组中，那么就需要遍历完整个数组才能得出结果，时间复杂度为O(n)。

由于目标元素的位置不同，导致时间复杂度出现量级差异。这种情况下就需要考虑平均情况时间复杂度，下面简单分析下：目标元素如果在数组中，出现的位置有n种情况，加上不在数组中这一种情况，总共n+1种情况。每种情况下需要遍历的次数如下表：

目标元素所在位置与遍历次数的关系

平均遍历次数=各种情况遍历次数相加÷总的情况数。

如果我们忽略掉系数和低阶项的话，那么计算公式就变成了

忽略之前

（1+2+3+...+n+n）/（n+1） = n(n+3) /2(n+1)

忽略之后，计算就变成了 n

也就是说他的平均时间复杂度变成了 T(n) = O(f(n)) = O(n)。

实际上有很多人说，计算这个平均时间复杂度没有任何意义，其实不是，他实际上就是一个衡量程序运行时间的标准，只有这样，我们才能看出这个算法的好，还是坏，你们觉得对么？

我们说完这个时间复杂度之后，我们需要开始关心这个空间复杂度了，那么什么是空间复杂度呢？

空间复杂度

我们所有的时间复杂度，是指程序的运行时间，那么空间复杂度同样的，指的时候程序运行的时，所需要占用的空间，记做S(n)=O(f(n))。

其实空间复杂度和时间复杂度比对起来就是一个挺有意思的事情，对于一个算法，他的时间复杂度和空间复杂度往往是相互影响的。

当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；

反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

而这个时间复杂度和空间复杂度组合起来，才能称之为复杂度。