[Algoritmo] Divide et impera
for l=1:length(v1)
for l2=1:length(v2)
if j2==1 && length(v2)>=2
for k1=1:20
if v1(k1)==v2(l2)
for k2=1:10
if v1(k2)==v2(l2)
end
end
end
end
if .....
if ........
else
end
else
end
end
Allora provo a calcolare il costo:
costo=O(length(v1)*[length(v2)*20*10]
la seconda parte lo vorrei risolvere con divide et impera ma non so individuare la n/b la a sarebbe pari ai sotto problemi che risulta pari a 2
Risposte
Ma dove sono le chiamate ricorsive?
"Cronovirus":
Ma dove sono le chiamate ricorsive?
E solo un esempio voglio solo sapere come si applica l'algoritmo
Quindi vuoi solo sapere come si fa l'analisi di un algoritmo divide et impera?
"Cronovirus":
Quindi vuoi solo sapere come si fa l'analisi di un algoritmo divide et impera?
si
Normalmente si scrive l'equazione di ricorrenza corrispondente e si calcola quindi la sua complessità a partire da quella. Ma ovviamente l'effettivo metodo usato dipende dall'algoritmo che si sta considerando.
"apatriarca":
Normalmente si scrive l'equazione di ricorrenza corrispondente e si calcola quindi la sua complessità a partire da quella. Ma ovviamente l'effettivo metodo usato dipende dall'algoritmo che si sta considerando.
per esempio
for j6=1:length(nodi_visitati)
[n1,m1]=size(self.vettore_percorso);
%possibili sorgenti
conta_edge=0;
conta_nodi_sorgenti=0;
%dimensione riga e colonna
for j2=1:m1
%verifico che la sorgente esiste nel
%vettore_percorso
if nodi_visitati(j6)==self.vettore_percorso(n1,j2)
%se esiste prelevo tutte le destinazioni del nodo
if nodi_visitati(j6)~=vb
edges2=ver.connectedEdges(edges,nodi_visitati(j6));
%copio in un vettore in una nuova riga e nella stessa colonna il valore
%della destinazione
display(nodi_visitati(j6));
display('edg');
display(edges2);
end
%tutte le destinazioni le imposto sorgenti
for j8=1:length(edges2)
conta_nodi_sorgenti=conta_nodi_sorgenti+1;
nodi_sorgenti(conta_nodi_sorgenti)=edges2(j8);
for k=1:vertices(1).n_vertices
for j=1:length(nodi_visitati_)
if self.s.vertice(k)==nodi_visitati_(j)
if strcmp(self.s.colore(k),colore_black)
display('nodo gia visitato');
nodi_visitati_(j)=0;
end
if strcmp(self.s.colore(k),'WHITE')
conta_impo_colore=1;
%impostazionen colore a grigio
self.s.colore(k)=colore_grey;
vertice.colore(k)=colore_grey;
%incremento del tempo di 1
self.time=self.time+1;
self.d_time=self.time;
vertice.d_time=self.time;
%impostazione del colore a nero
self.s.colore(k)=colore_black;
vertice.colore(k)=colore_black;
%incremento del tempo di 1
self.time=self.time+1;
vertice.f_time=self.time;
display('tempo1');
display(self.time);
end
end
end
%b1=O(1)+sommatoria
%length(nodi_visitati)(3O(1)+O(1)+11O(1))
end
end
[n2,m2]=size(self.vettore_percorso);
%scorro le righe
%copio i valori in una nuova colonna
%dei valori in quanto esisite un
%nuovo percorso
for k=1:n2
for j=1:length(edges2)
self.vettore_percorso(k,m2+j)=self.vettore_percorso(k,j2);
self.vettore_percorso(n2+1,m2+j)=edges2(j);
end
end
end
end
end
end
Salve,
come si applica a questo caso l'algoritmo divide et impera? e se ci fosse un ciclo for all'interno?
if h_cappelletto(1,j2)<=sum(h_senza_cappelletto(1,1:j2))
if h_cappelletto(1,j2)+sum(g_cappelletto(1,1:j2))<=sum(gn0_senza_cappelletto(1,1:j2))+hn0_senza_cappelletto(1,j2)
display('condizione su h è verificata al passo');
display(conta_passo);
condizione_h=1;
else
display('condizione su h non è stata verificata');
condizione_h=0;
nodi_adiacenti2(j4)=[];
end
else
display('condizione su h non è stata verificata');
end
come si applica a questo caso l'algoritmo divide et impera? e se ci fosse un ciclo for all'interno?
Abbi pazienza.. non puoi pretendere che qualcuno si metta a leggere codice illeggibile e senza alcun senso
"Cronovirus":
Abbi pazienza.. non puoi pretendere che qualcuno si metta a leggere codice illeggibile e senza alcun senso
devo per forza calcolarlo
Salve, ha ragione partiamo dalle basi
for j6=1:length(nodi_visitati)
vertices.conta_righe=vertices.conta_righe+1;
%copio solo una alla volta la prima sorgente
if vertices.conta_righe==1
for j=1:length(nodi_visitati)
self.vettore_percorso(vertices.conta_righe,j)=nodi_visitati(j6);
display(self.vettore_percorso);
end
end
%Costo:O(length(nodi_visitati)^2
[n1,m1]=size(self.vettore_percorso);
for j2=1:m1
if nodi_visitati(j6)==self.vettore_percorso(n1,j2)
if self.vettore_percorso(n1,j2)~=vb
for j=1:length(edges3)
[n2,m2]=size(self.vettore_percorso);
for k=1:n1
self.vettore_percorso(k,m2+j)=self.vettore_percorso(k,j2);
end
self.vettore_percorso(n2+1,m2+j)=edges3(j);
end
end
%Costo 2:O[n1+length(edges3)]*m1
e se volessi applicare divid[size=200]E[/size] et impera?
Divide et impera è per definizione un particolare approccio alla programmazione e il tuo codice non la usa. Spero di aver risposto alla tua domanda
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo