算法的空间复杂度
一.程序运行时的内存需求:
二.空间复杂度:
例一:
形参n和i各占4个字节,共8字节,是常数,可忽略。而数组flag所占字节是4 * n个,不是常数,不可忽略
例二:
例三:
三.函数递归调用带来的内存开销:
例一:
n为5和n为4时都有a,b,c的创建,只是地址不同,n为其他值时也一样。
形参n和a,b,c都固定各占4个字节,共16个字节,所以每一次函数调用都大概需要16个字节来存储相应的信息
即每一次aB个内存,而且共n次,刚好共占naB个内存
例二:
数组flag所占字节和n有关,每一次函数调用n都会变化,因此flag所占字节每一次都会变化。