数据结构学习day1
有关算法的时间复杂度与空间复杂度
1.算法的时间复杂度
指事先预估算法的时间开销T(n)和问题规模n的关系.
2.算法的空间复杂度
3.对于空间复杂度,有几种情况:
一是代码中只有一般的顺序语句,那么占用的内存空间则是常数个,与问题规模n无关,空间复杂度就是O(1).
二是代码中有一些特别的储存结构,如数组int[n],那么空间复杂度就为4n+k,空间复杂度就是O(n)了.或者定义二位数组时空间复杂度可能就是O(nn)了.
三是递归也是会影响到空间复杂度的:
举一个简单地代码
这里的空间复杂度就为kn(每层都声明一次a,b,c,n等,共需进行n次),所以复杂度为O(n).
当递归中含有数组等类型时
由于数组长度和问题规模相等,那么每次调用时开辟的空间也不同,空间复杂度为1+2+3+…+n=n(n+1)/2=O(nn).