计算一个程序的空间复杂度
template<class T>T Abc(T&a,T&b,T&c)
{return a+b+b*c+(a+b-c)/(a+b)+4;
}
书上说的我一点都看不懂,不知道这里有没有人能帮我详细解释一下如何计算一个程序的空间复杂度。我现在是自学算法,刚开始感觉有点吃力,还望大家多多帮助啊 感谢大家
S(P)=C+S(p)(实例特征)
在估算S(p)之前,必须选择分析所使用的实例特征。两种可能性是:1,数据类型T;2.a,b,c的大小。假定使用T作为实例特征。由于a,b,c是引用参数,所以在函数中不需要为他们的值分配空间,但是必须保存指向这些参数的指针。如果每个指针需要2个字节,那么就是6个字节的指针空间。因此函数所需要分配总空间是个常量,S(abc)=0。如果用abc的大小作实例特征。则S(abc)=0。
-------------------------------------------
为什么不管如何S(abc)=0呢?
[此贴子已经被作者于2006-6-19 12:55:08编辑过]