Domande con tag 'big-o'

domande con tag
1
risposta

Calcola Big-O per cicli nidificati

Ho trovato questo ciclo annidato per calcolare la notazione Big-O. for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) Ho ottenuto la complessità temporale dell'algoritmo con questa equazione polinomiale. Supponiamo che C1,...
posta 27.04.2015 - 07:19
2
risposte

Che cos'è un algoritmo O (n) per risolvere questo enigma?

Organizzeremo un incontro in cui tutti parleranno in senso orario attorno a un tavolo. Ci sono n persone con n punti. Ogni persona ha una preferenza di posizione (ad esempio, alcuni vogliono andare per primi, altri per ultimi, ecc.). Tutti sono...
posta 13.03.2014 - 09:56
2
risposte

Ricerca binaria O (log (n)) o O (n)

Vedo dove la maggior parte delle letture online deriva dal fatto che la notazione Big-Oh di una ricerca binaria è O (log (n)), ma questo non presuppone un albero bilanciato? Cosa succede se l'albero è completamente sbilanciato (ad esempio simile...
posta 20.04.2016 - 03:45
1
risposta

Notazione per la complessità temporale media di un algoritmo

Quale notazione usi per la media complessità temporale di un algoritmo? Mi viene in mente che il modo corretto sarebbe usare il big-theta per riferirsi a un insieme di risultati (anche quando una prova specifica può differire). Ad esempio, la...
posta 11.05.2013 - 07:46
3
risposte

Qual è la complessità O grande di questo algoritmo ricorsivo?

Sto seguendo un corso di Algoritmi e Strutture Dati. Oggi, il mio professore ha detto che la complessità del seguente algoritmo è 2^n . Ho aspettato che la lezione finisse, mi sono avvicinato e gli ho detto che credevo davvero che foss...
posta 15.10.2015 - 22:07
3
risposte

Notazione Big O di casualità

Stavo pensando ad algoritmi inefficienti basati sulla casualità e mi sono chiesto come classificarli. Per esempio. Supponi di voler generare tutti i numeri da 1 a N in ordine casuale ma solo una volta ciascuno. Il mio algoritmo inefficient...
posta 14.05.2015 - 10:44
1
risposta

Notazione Big-O e problemi di interruzione

Sto cercando di capire perché è impossibile creare uno strumento che calcoli automaticamente la notazione Big-O. Ho letto dei problemi di Halting, ma non sono relativo alla notazione Big-O e mi stavo chiedendo, o almeno ho un esempio in cui n...
posta 01.08.2016 - 11:12
1
risposta

Complessità delle chiamate ricorsive

il mio cervello è un po 'bloccato mentre sto cercando di compilare un esempio per il mio blog. Sto presentando un algoritmo che disegna un numero da un array, lo aggiunge a una somma e si chiama in modo ricorsivo. func solve(coins: Array<In...
posta 05.04.2016 - 10:51
1
risposta

omega perché K + N meglio di N

Stavo rivedendo il grande cheatsheet di O al link e ho trovato alcune voci sotto ordinamento che non capisco. I runtime sono codificati a colori, il verde è migliore del giallo. Ci sono casi in cui Ω (N) è codificato a colori meglio di Ω (N...
posta 16.09.2016 - 22:18
1
risposta

Come è possibile eseguire un'operazione di vertice di aggiunta in un tempo costante per un grafico rappresentato utilizzando l'elenco di adiacenza?

L'aggiunta di un vertice in un grafico rappresentato utilizzando un elenco di adiacenze richiede O (1) complessità temporale in base al collegamento (operazione di grafico > adjacency list > add vertice). Si dice che l'elenco di adiac...
posta 20.09.2015 - 15:08