一.算法的复杂度:
二:时间复杂度:
1.时间复杂度的概念:
在计算机科学中,算法的时间复杂度是一个函数(这里的函数指的是数学中的函数),它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
上述代码中,时间复杂度是多少?(在没有深层学习的情况下浅浅分析)
首先两个嵌套循环,循环条件都是小于N,所以在这个嵌套的循环时间复杂度就是N^2,接下来还有一个循环,这个循环是一个单层循环,循环条件小于2*N,所以时间复杂度就是2*N,还有一个循环是当M>0的时候执行,所以循环次数是10次,总的来说这个代码的时间复杂度就是N^2+2*N+10。在这里只是简单分析是这个,但其实真正的时间复杂度不能这么算,在这个表达式可以看出,当N非常大的时候对时间复杂度的影响只有N^2这个表达式。
2.大O的渐进表示法:
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
3.通过例题来算时间复杂度:
1.
分析如下:
2.
分析如下:
3.
4.
这个strchr函数就是在一个字符串中查找一个字符
分析图:
5.冒泡排序的时间复杂度:
第二张图可以更加直观看出冒泡排序循环的次数,也就可以更好计算出时间复杂度是多少
6.
根据图解即可看出递归调用的复杂度就是O(N),递归的时间复杂度就是相加,就是看你N是多少了。
7.
根据图解可以看出,虽然计算出最后结果为2^(N-1)-1但是根据时间复杂度计算规律其实就是O(2^N).
三.常见复杂度对比:
在这里试一下时间复杂度是O(N^3)时可以看到程序崩溃了,说明此时时间复杂度太大,这里运用clock函数记录运行前后时间然后相减来看出时间,可是这里时间打印不出来。
所以当时间复杂度越来越大时对程序有损害,并且运行吃力,所以要选择最少的时间复杂度的算法。
四.消失的数字和轮转数组:
1.消失的数字:
这个题目有时间复杂度的要求,要求必须在O(n)的时间内完成。
思路一:
一开始的思路是先给这个数组排序,排完序之后如果前面数字+1等于后面数字就是正确的,如果不是就是缺少那一个。但是排序可以用qsort函数,也可以使用冒泡排序,但是qsort函数的时间复杂度是O(logN*N)不符合题目要求,而冒泡排序的时间复杂度是O(N^2),所以这两个都不符合,所以这个思路有错误。
思路二:
这是一个等差数组,我们直接对0~N进行就和,然后再利用一层循环将求和的结果与数组的每个元素相减,这样就可以找到消失的那个数字了。
这就是在力扣上的答案。这个时间复杂度刚好是O(N) 刚好满足题目的要求
思路三:
这里我们可以用异或的第三个性质,一开始先让0与数组的元素(没有缺少的元素)异或,之后再与0~N异或这样操作完的结果就是缺失的那个数字
拿例子一来测试,1到3现在缺少数字2
这样在第一个循环中0^3^0^1 然后再在第二个循环中进行异或操作0^3^0^1 ^0^1^2^3 再根据上面异或的自反性就可以看出结果就是消失的那个数字,这样返回结果即可。这样的思路时间复杂度也是O(N)也是符合题目要求的。
2.轮转数组:
首先可以看出当旋转是数组个数的整数倍时其实就等于没有旋转,所以在旋转前可以取余看看真正需要旋转多少次。
思路1:
根据思路1可以写出代码:
但是这种方法行不通,在最后一个用例上超出了时间限制,也就是说这种方法时间复杂度高了,这个代码的时间复杂度是O(N^2)。
思路二:
这种方法不好想到,比较难
根据这个思路,我们要先写一个逆置函数,并且要弄清楚逆置的区间。
根据上述思路写出逆置函数:
再根据上面的区间可以写出完整代码:
在这里编译也是通过了,在这个代码中时间复杂度就是O(N)。所以思路二优于思路一
五.空间复杂度:
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。
1.
计算空间复杂度是看解决这个问题开辟的额外的空间,在这里可以看出整形指针a和整形n是题目给的,在这里另外给了end 和i还有exchange这三个变量,属于解决这个问题另外开辟的空间,使用了常数个额外的空间,则空间复杂度就是O(1)。
2.
递归每递归一次开辟一个新的空间,也就是栈帧,使用了N次所以其空间复杂度也就是O(N)。
总的来说空间复杂度常见的是这三个:O(1),O(N),O(2^N).