Pages: [1]   Go Down
Print
Author Topic: Alcune domande dei compiti  (Read 831 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 18-09-2012, 10:59:18 »

Ho dei dubbi su alcune domande:

1)Array di n interi. Qual'è la complessità del miglior algoritmo possibile per creare dall'array un albero binario di ricerca?
O(n) -  O(nlgn) - O(n^2 lgn) - O(n^2).   

2)Sia T un albero binario di ricerca. Il numero minimo di confronti per trovare l'elemento più piccolo?
Risposta mia: O(1)?

3)Sia T un albero binario di ricerca con tutti e soli i numeri compresi da 1 a 100. Per cercare il numero 50, quanti numeri maggiori di 50 possiamo trovare?
Tutti i numeri > di 50, al più la metà di tali numeri, al più log 50 numeri maggiori di 50, nessuno dei precedenti.

Sapete rispondere per caso?
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #1 on: 18-09-2012, 22:11:53 »

Nessuno?
Logged
LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #2 on: 29-09-2012, 15:09:51 »

1. Il counting sort consente di ordinare un array A in tempo O(n), se max(A) è nell'ordine di n.
Successivamente da questo array puoi creare un BST completamente sbilanciato in tempo O(n). Quindi per me la risposta è la prima.
Sono quasi sicuro che sia possibile anche creare un BST bilanciato ma al momento l'unica cosa che mi viene in mente è O(nlogn).
La domanda non chiede comunque di ottenere un BST decente quindi secondo me dovrebbe andar bene comunque.

2. Beh partendo dalla radice devi prendere sempre il figlio a sinistra fino alla prima foglia, e quello è il minimo.
Sicuramente non si può fare in tempo costante.
Devi considerare l'altezza dell'albero (h) e il numero di nodi (n).
Nel caso peggiore l'albero è sbilanciato, e quindi hai h=n → O(n).
Nel caso di albero bilanciato h=log₂(n) e quindi si ha O(log n).. però solo se sai che l'albero è bilanciato.



La 3 è facile, se l'albero è completamente sbilanciato al punto da diventare una lista (che è il caso peggiore), puoi trovare al più tutti i numeri >50 prima di arrivare a 50.

Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
Pages: [1]   Go Up
Print
Jump to: