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

要说复杂性，那一定和你自己的算法有关，所以总有人会说，我不知道算法是什么，但也不会耽误我的发展。这么说，但你应该考虑一下。如果面试官在你面试大厂的时候给他提出了这个问题，你可以说，虽然我不太擅长，但我可以工作。我想面试官可能不相信你。工作时，只要程序能跑，不太注意性能，所以尽量避开坑（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 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))。

事实上，与时间复杂性相比，空间复杂性是一件非常有趣的事情。对于算法来说，他的时间复杂性和空间复杂性往往相互影响。

当追求更好的时间复杂性时，空间复杂性的性能可能会变差，这可能会导致更多的存储空间；

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

这种时间复杂度和空间复杂度的结合可以称为复杂度。

你明白了么？