面试的时候,总有面试官喜欢问,时间复杂,空间复杂,比如O(n2) 这样,那么如何定义这种时间复杂性,为什么使用这种定义,最终的时间复杂性与你的程序有什么关系呢?今天,让我们谈谈你对复杂性的看法。
算法
要说复杂性,那一定和你自己的算法有关,所以总有人会说,我不知道算法是什么,但也不会耽误我的发展。这么说,但你应该考虑一下。如果面试官在你面试大厂的时候给他提出了这个问题,你可以说,虽然我不太擅长,但我可以工作。我想面试官可能不相信你。工作时,只要程序能跑,不太注意性能,所以尽量避开坑(ArrayList Or LinkedList),用哪个简单,但只要面试数据结构和算法,就必须跪下。
如果你是专业人士,你肯定会对算法有一些概念,因为你可能会在大学里学习数据结构和算法,但如果你只想通过考试,你就不会说了。
那算法是什么呢?
算法(Algorithm)是指对解决问题的准确、完整的描述,是一系列解决问题的明确指令,算法代表着用系统的方法来描述解决问题的战略机制。
算法实际上是用一种流行的语言来说的,这是一种结论的想法,算法,没有对错,但有好与坏的区别。
例如,我们日常生活中最常见的算法是排序中的算法
- 冒泡排序
- 快速排序
- 插入排序
- 归并排序
- 计数排序
还有其他算法,LRU 算法,LFU算法,Hash算法可以实现相同的功能,但没有错,即效率和时间复杂性。 时间复杂度是什么呢?
时间复杂度
其实说白了,就是你写的算法,运行的时间,而这个时间在设计层面,就可以称之为时间复杂。
我们假设执行一行代码的时间是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个位置 | 遍历2次 |
第3个位置 | 遍历3次 |
第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))。
事实上,与时间复杂性相比,空间复杂性是一件非常有趣的事情。对于算法来说,他的时间复杂性和空间复杂性往往相互影响。
当追求更好的时间复杂性时,空间复杂性的性能可能会变差,这可能会导致更多的存储空间;
反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。
这种时间复杂度和空间复杂度的结合可以称为复杂度。
你明白了么?