如何替换网站上的动画,辽宁省网站备案,龙岗区网站制作,做网站要找什么公司1.空间复杂度的定义
算法在临时占用储存空间大小的量度#xff08;就是完成这个算法所额外开辟的空间#xff09;#xff0c;空间复杂度也使用大O渐进表示法来表示
注#xff1a; 函数在运行时所需要的栈空间(储存参数#xff0c;局部变量#xff0c;一些寄存器信息等)…1.空间复杂度的定义
算法在临时占用储存空间大小的量度就是完成这个算法所额外开辟的空间空间复杂度也使用大O渐进表示法来表示
注 函数在运行时所需要的栈空间(储存参数局部变量一些寄存器信息等)在编译期间就已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定 例1
int* fib(int n)
{int* fibarray (int*)malloc(sizeof(int) * (n));if (n 0){return NULL;}fibarray[0] 1;fibarray[1] 1;for (int i 2; i n; i){fibarray[i] fibarray[i - 1] fibarray[i - 2];}return fibarray;}
怎么查看这段代码的空间复杂度可以观察到该段代码为了完成这个算法额外申请了n个空间即空间复杂度O(n)
例2
void Bubble_Sort(int a[], int n)
{assert(a);int exchange 0;for (int end n; end 1; --end){for (int begin 1; begin end; begin){if (a[begin] a[begin - 1]){Swap(a[begin], a[begin - 1]);exchange 1;}}if (!exchange){break;}}
}
可以观察到这段代码完成这个算法额外开辟了三个空间 即空间复杂度O(1)
例3
int fac(int N)
{if(N 0){return 1;}return fac(N-1)*N;
}
这段递归的空间复杂度为多少了
注每次递归都是开辟新的空间来进行操作
这段代码从Fac(N) 开始 Fac(N - 1)Fac(N - 2).....Fac(1)Fac(0)所以递归了N次
该算法完成递归额外开辟了N个空间O(N)
我们来看一段代码
void F1()
{int b 0;printf(%p , b);
}void F2()
{int a 0;printf(%p , a);
}int main()
{F1();F2();return 0;
}
F1和F2是否使用的同一个空间
运行结果 可以看到这两个不同函数中的变量居然是用的同一个地址
原因因为mian函数中是先调用的F1在F1执行完之后F1所在的空间被系统收回了即在执行F2时F2也是用的这个地址因此F2和F1所用的空间相同
例4
long long Fib(int N)
{if (N 3){return 1;}return Fib(N - 1) Fib(N - 2);
}
这段代码的时间复杂度为O(2^N) 递归时Fib(N) —— Fib(N - 1) 和 Fib(N - 2),然后编译器是先将Fib(N - 1)先递归完再进行Fib(N - 2)
递归到最后Fib(2) Fib(1)时先执行的是Fib(2)随后就是Fib(1)所以可以推断Fib(1)所用的空间是Fib(2)所释放的空间所以Fib(1)和Fib(2)所用的空间是一样的所以跟着这个思路往上推假如N 5 Fib(5)就额外开辟了4个空间
如图 一共额外开辟了4个空间
这段代码的时间复杂度;O(2^N) 时间一去不复返这次不可能执行上一次的操作不可重复利用
空间复杂度O(N) 空间用了之后归还可以重复利用
