die laufzeit einer rekrusiven methode fixen

[MudGuard]

Hi,

  

> 		for(int n=0;n<nachfolger.size();n++)//alle in der naechsten zeiteinheit zu erreichende  
> 		{  
> 			if(map.containsKey(nachfolger.get(n).id))  
> 			{  
> 				if(d[t]!=0){  
> 					return p(map,nachfolger.get(n).id,t,T);  
> 				}  
> 			}  
> 			else  
> 				if(d[t]!=0){  
> 					return p(map,nachfolger.get(n).id,t,T);  
> 				}  
> 			}  
> 		}  
> 		return map;  
> 		  
> 	}  
> 

Es wird also pro Schleifendurchlauf noch ein rekursiver Aufruf gemacht, der Schleifendurchlauf ist schon O(n).
Bei einer Ebene der Rekursion sind wir also schon bei O(n*n), bei 2 Ebenen bei O(n*n*n), bei m Ebenen bei O(n^m)
Die Anzahl der Ebenen ergibt sich bei Dir, wenn ich das richtig sehe, aus T - t (+/- 1, das rauszufummeln ist mir jetzt zu doof).
Deine Funktion ist also O(n^(T-t)), nicht O(n) wie von Dir vermutet.

cu,
Andreas