[JAVA] Calcolo complessità metodo ricorsivo

[TheDragon81]

Salve,
qualcuno mi può aiutare a trovare la complessità computazionale (asintotica) di questo metodo ricorsivo? Grazie in anticipo.

private static void antichainCreator(Node lastNode, ArrayList<Node> antiChain){
	_hashChoicelist =  new Hashtable<Node, ArrayList<String>>();
	_hashChoicelist.put(lastNode,lastNode.getElementList());
	if(!_hashChoicelist.get(lastNode).isEmpty()){
		ArrayList<String> next = _hashChoicelist.get(lastNode);
		for (int i = 0; i < next.size(); i++){
			Node focus = _hashNodeList.get(next.get(i));
			if (!antiChain.contains(focus) 
					&& focus.isGood(antiChain)){
				ArrayList<Node> antiChainTemp = (ArrayList<Node>)antiChain.clone();
				antiChainTemp.add(focus);
				antichainCreator(focus, antiChainTemp);
			} else {
				if(!_antiChainList.contains(antiChain)){
					_antiChainList.add(antiChain);
					_antichainMax(antiChain);
				}
			}
		}
	}
}

dove il metodo "isGood" è questo:

public boolean isGood(ArrayList<Node> antiChain){
	boolean check = true;
	for(int i=0; i < antiChain.size();i++){
		if(antiChain.get(i).isInBlackList(_name)){
			check = false;
			break;
		}
	}
	return check;
}

public boolean isInBlackList(String elem){
	return(_blacklist.contains(elem));
}

[TheDragon81]

Uppolo

[banryu79]

Sarebbe meglio che prima postassi il tuo tentativo di risoluzione del problema, magari indicando i dubbi specifici che hai: così chi ti legge può aiutarti, altrimenti l'alternativa sarebbe rispondere direttamente ma il regolamento di questa sezione del forum vieta di postare soluzioni complete ad esercizi.

[TheDragon81]

Originariamente inviato da banryu79

Sarebbe meglio che prima postassi il tuo tentativo di risoluzione del problema, magari indicando i dubbi specifici che hai: così chi ti legge può aiutarti, altrimenti l'alternativa sarebbe rispondere direttamente ma il regolamento di questa sezione del forum vieta di postare soluzioni complete ad esercizi.

Beh, non è una soluzione ad un esercizio ... questo algoritmo l'abbiam creato io ed un mio amico per calcolare le anticatene di un grafo ...
Cmq avevamo pensato a O(n^2) ... cmq non ci convince quell' isGood (che nel caso pessimo si cicla tutta la lista ...)

[banryu79]

Non me ne intendo di complessità computazionale, però avete tenuto conto anche delle chiamate al metodo contains? In teoria hanno costo lineare anche quelle, almeno a leggere la javadoc:

Originariamente inviato da javadoc per ArrayList<E> class

...
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
...

Quindi, se non sbaglio, il metodo isInBlackList ha complessità lineare, e di conseguenza il metodo isGood che lo richiama nel suo ciclo for ha complessità O(n^2).

Ma aspetta qualcuno di più esperto, ripeto, sono ignorante in materia

[TheDragon81]

Originariamente inviato da banryu79

Non me ne intendo di complessità computazionale, però avete tenuto conto anche delle chiamate al metodo contains? In teoria hanno costo lineare anche quelle, almeno a leggere la javadoc:


Quindi, se non sbaglio, il metodo isInBlackList ha complessità lineare, e di conseguenza il metodo isGood che lo richiama nel suo ciclo for ha complessità O(n^2).

Ma aspetta qualcuno di più esperto, ripeto, sono ignorante in materia

Quindi, tornando al metodo principale (e quindi al ciclo che contiene il tutto) diventerebbe un O(n^3)?

[_Claudio]

Da quanto ho capito ipotizzando che le chiamate a funzioni di libreria abbiano tutte costo costante ho che dentro antiChainCreator chiamo isGood che nel caso pessimo costa n e antiChainCreator che nel caso pessimo costa n^n perchè chiama se stessa n volte e per tutte le n volte cicla sugli n elementi, essendo funzioni in serie queste complessità si sommano pertanto la complessità nel caso pessimo asintotica è O(n^n).

Ovviamente non è l'apocalisse questa perchè alcuni algoritmi hanno complessità O(n^n) ma il caso pessimo ha una probabilità bassissima di accadimento e nei casi medio e ottimo hanno una complessità migliore di altri.

Sta a te valutare in base a come è stato ideato se sei in tali condizioni ottimali.

Poi si sa che la ricorsione quando vi sono cicli di mezzo costa molto in termini di computazione e risorse sotto caso pessimo, anche perchè a mio avviso è diabolico usare un ciclo dentro una funzione ricorsiva come in questo caso, e se lo si fa bisogna essere ben consapevoli di quello che si sta facendo.

[malocchio]

Originariamente inviato da _Claudio

Da quanto ho capito ipotizzando che le chiamate a funzioni di libreria abbiano tutte costo costante ho che dentro antiChainCreator chiamo isGood che nel caso pessimo costa n e antiChainCreator che nel caso pessimo costa n^n perchè chiama se stessa n volte e per tutte le n volte cicla sugli n elementi, essendo funzioni in serie queste complessità si sommano pertanto la complessità nel caso pessimo asintotica è O(n^n).

Ovviamente non è l'apocalisse questa perchè alcuni algoritmi hanno complessità O(n^n) ma il caso pessimo ha una probabilità bassissima di accadimento e nei casi medio e ottimo hanno una complessità migliore di altri.

Sta a te valutare in base a come è stato ideato se sei in tali condizioni ottimali.

Poi si sa che la ricorsione quando vi sono cicli di mezzo costa molto in termini di computazione e risorse sotto caso pessimo, anche perchè a mio avviso è diabolico usare un ciclo dentro una funzione ricorsiva come in questo caso, e se lo si fa bisogna essere ben consapevoli di quello che si sta facendo.

Sì anche secondo me è nⁿ (notare l'uso del carattere speciale )

E rabbrividisco