Domande con tag 'big-o'

domande con tag
1
risposta

Complessità del tempo quando la variabile del ciclo dipende dalla variabile del ciclo esterno

Qual è la complessità temporale del seguente pezzo di codice nel peggiore dei casi? s = 0; for( i = 1; i <= n; ++i ) { for( j = 1; j <= i * i; j++ ) { for( k = 1; k <= j and j % i == 0; k++ ) s++; } } Og...
posta 26.10.2015 - 19:03
1
risposta

Algoritmo di distribuzione dei semi con complessità migliore di O (n ^ 3)?

Ho incluso il mio approccio e la mia soluzione. La mia soluzione funziona bene, tuttavia, non è ottimizzata con la complessità di O (n ^ 3) Un ONG sta eseguendo un programma di distribuzione dei semi. Ha una quantità limitata di semi di qua...
posta 09.07.2015 - 16:28
4
risposte

Trovare il primo subarray che sommi a un dato totale

Ecco la domanda: Given and unordered array of positive and negative integers. How can you find the first subarray to sum to a given value? Ad esempio. Dato l'array ... [1, -3, 4, 8, 2, -14, 3, -1, 10, 6] Trova il primo subarray da s...
posta 14.03.2015 - 23:51
1
risposta

Se sostituisco N oggetti con N puntatori, la mia complessità spaziale è ancora O (N)?

Diciamo che ottengo N oggetti come input, e ho bisogno di riorganizzarli in una diversa struttura dati. Ciò significa che la complessità dello spazio del mio algoritmo sarà O(N) . Ma cosa succede se sostituisco gli oggetti con i puntato...
posta 15.01.2015 - 03:03
3
risposte

Perché la complessità del recupero di un valore da un array è O (1)?

Come mai la complessità del recupero di un valore da un array in base all'indice è O (1)? Ho pensato che l'algoritmo debba passare attraverso tutti gli indici, trovare l'indice corretto e quindi sapere quale valore restituire. Ciò significa c...
posta 06.08.2014 - 01:40
3
risposte

Cosa sono O (m + n) e O (m * n) nella notazione Big O? [duplicare]

Comprendo che O(n) descrive un algoritmo le cui prestazioni cresceranno in modo lineare e proporzionale alla dimensione del set di dati di input. Un esempio di questo è un ciclo for: for n in 0.100 puts n end Che cosa significa O...
posta 08.09.2015 - 00:41
2
risposte

Costanti e Big O [duplicato]

Le costanti sono sempre irrilevanti anche se sono grandi? Ad esempio è O (10 ^ 9 * N) == O (N)?     
posta 09.04.2013 - 01:35
3
risposte

Big O Complessità quando si itera in 3 dimensioni

Che complessità temporale classificheresti come segue? int n = 100; for(int x = 0; x < n; x++) for(int y = 0; y < n; y++) for(int z = 0; z < n; z++) DoWork(x,y,z); Non credo che qualcuno possa obiettare che...
posta 07.12.2018 - 18:50
5
risposte

BIG O - Algoritmo Case Analysis

Perché il grande O è più comunemente associato alle complessità del caso peggiore e al caso medio di una funzione     
posta 11.05.2011 - 21:58
1
risposta

Mi è stato permesso di semplificare i termini durante il calcolo di Big O?

Voglio calcolare il runtime della seguente funzione T (n) = (1 + 2 + 3 + 4 + 5 + ... + n) / n All'inizio questo non mi è sembrato difficile perché può essere risolto facilmente trasformando la formula T (n) = (n (n-1) / 2) / n = (n ^ 2-...
posta 20.01.2018 - 14:48