面试时候常说的复杂度到底是什么？

本文主要是介绍面试时候常说的复杂度到底是什么？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试时候常说的复杂度到底是什么？

我们在面试的时候，总有面试官喜欢问，时间复杂度，空间复杂度，就比如像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种情况。每种情况下需要遍历的次数如下表：

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