如何分析 recursive function 的复杂性# Java - 爪哇娇娃
l*0
1 楼
比如分析这两个算法:
int nth(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return nth(n-1) + nth(n-2);
}
int nth(int n, Map map){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
if( !map.containsKey(n) ){
map.put(n, nth(n-1,map) + nth(n-2,map));
}
return map.get(n);
}
int nth(int n){
if(n==0){
return 0;
}
if(n==1){
return 1;
}
return nth(n-1) + nth(n-2);
}
int nth(int n, Map
if(n==0){
return 0;
}
if(n==1){
return 1;
}
if( !map.containsKey(n) ){
map.put(n, nth(n-1,map) + nth(n-2,map));
}
return map.get(n);
}