安庆信德建设咨询有限公司网站,成都中小企业网站建设,学编程有什么好处,县检察院门户网站建设情况本篇总结函数调用过程会存在的一些奇怪现象#xff0c;空间复用问题#xff0c;其实本质上涉及函数调用的底层原理#xff0c;理解函数栈帧的创建和销毁这样的问题直接迎刃而解。1.空间复用问题案例1案例22.函数调用过程不清晰问题案例33.总结1.空间复用问题
案例1
我们先…
本篇总结函数调用过程会存在的一些奇怪现象空间复用问题其实本质上涉及函数调用的底层原理理解函数栈帧的创建和销毁这样的问题直接迎刃而解。1.空间复用问题案例1案例22.函数调用过程不清晰问题案例33.总结1.空间复用问题
案例1
我们先来看一个代码
void F1()
{int a 10;printf(%p\n, a);
}
void F2()
{int b 10;printf(%p\n, b);
}
int main()
{F1();F2();return 0;
}F1和F2函数的操作基本一样你说它们所开辟的空间的地址是同一块吗 或者说a和b的地址是一样的吗
结果是一样的。为什么呢 我们知道调用函数需要给函数开辟栈帧也就是开辟空间而栈帧是在堆区开辟的 当函数使用完后该函数栈帧就要销毁。 但不是真正意义上的销毁而是把使用该空间的权限还给操作系统这片区域不再受你操控。
所以我们在调用F1()函数时操作系统先给F1()开辟栈帧给变量a分配内存。然后当F1()函数结束时该空间又被操作系统收回 接着又调用F2()函数操作系统又将刚刚收回的空间又分配给F2()函数。 所以F1函数和F2函数使用的空间地址是一样的变量a和变量b的地址也就是一样的。 案例2
这是一个阶乘递归的代码
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
int main()
{long long n;Fac(n);return 0;
}请问它的空间复杂度和时间复杂度是多少呢
函数Fac每次调用都会返回Fac(n-1)*n,直到N0时才返回1. 也就是递归了n次所以时间复杂度为O(n). 而空间复杂度呢 因为Fac函数每次调用自己都会开辟一个函数栈帧调用了n次所以开辟了n个空间。 所以空间复杂度也是O(n). 那想一下Fac(n)与Fac(n-1)与Fac(n-2)…等函数的空间地址是同一块空间吗
综合上面的案例我们应该判断它们不是同一块空间的。
为什么呢 上面的案例是F1函数调用完,结束后再调用的F2函数 而阶乘递归是属于嵌套调用每个函数都还没完全结束就又调用另一个函数了所以它们开辟的空间肯定不一样它们各自使用的空间都没有被操作系统收回过怎么可能有其他函数又去占用这块空间呢。
而对案例修改一下也可以让F1和F2函数的地址不一样也就是在F1函数的内部去调用函数F2这样它们的空间就不会重复了。
如下所示
void F1()
{int a 10;printf(%p\n, a);F2
}
void F2()
{int b 10;printf(%p\n, b);
}
int main()
{F1();return 0;
}2.函数调用过程不清晰问题
案例3
这是一个斐波那契契递归Fib
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
int main()
{long long n;Fib(n);return 0;
}你知道这个递归Fib函数的空间复杂度和时间复杂度吗 Fib(n)函数每次返回两个函数Fib(n-1)Fib(n-2).直到n3时返回1. 也就是Fib函数每次调用都会又调用两个函数而这个两个函数相当于又调用4个函数依次类推…最后应该调用2^n次 所以时间复杂度为O(2^n). 那空间复杂度呢空间复杂度是多少呢 有的人可能想呀它不是相当于调用了2 ^ n次嘛那不就是申请了2 ^ n个空间吗。真的是这样吗
可能现在还有很多人没有搞清楚函数是怎么调用的递归是怎么调用的。 有的人可能想是Fib(n)调用Fib(n-1)和Fib(n-2),然后操作系统就给Fib(n-1)和Fib(n-2)分配栈帧了但其实不是。 函数的调用只有完全调用完才能去执行下一步。 调用Fib(n-1)后其实会继续往下面调用Fib(n-2),然后再往下调用Fib(n-3)直到调用到Fib(2),Fib(2)返回1后Fib(2)也就结束函数栈帧销毁回到F(3)F(3)这时才开始调用F(1),F(1)返回1F(1)的栈帧销毁返回F(3)F(2)又开始调用了。依次类推 Fib(2)返回后操作系统是不是就将它的空间回收了然后又调用了Fib1所以Fib(1)开辟的空间就是刚刚操作系统收回的空间呀。 其实就是左边Fib(2)和右边F(1)用的是同一块空间。依次类推Fib(4)返回后空间被收回然后操作系统又将空间分配给右边的Fib(3)使用。所以大体上左边和右边是共用一块空间而左边是调用了n个空间所以最后的空间大小是O(n).
3.总结
这三个个案例本质上就是要搞清楚函数栈帧是如何创建的以及如何销毁的。
搞清楚函数是如何调用的调用前操作系统要给函数分配栈帧调用函数结束后操作系统要将栈帧收回。 如果对函数栈帧方面有兴趣的可以阅读一下博主的《细谈函数栈帧的创建与销毁》。 还有我们可以发现 时间是一去不复返的不可再重复利用。 而空间是可以重复利用的。所以我们要特别重视算法的时间效率。
