Domande con tag 'big-o'

domande con tag
1
risposta

Algoritmo di ordinamento più rapido per ordinare un numero basso di numeri interi

Sto facendo un programma sul mio tempo libero che voglio correre il più rapidamente possibile. Il programma è scritto in C. Un ampio set di procedure funziona su puntatori a 7 numeri interi ordinati in base ai loro valori numerici da alto a b...
posta 08.11.2014 - 15:06
3
risposte

Trovare la sottosequenza più lunga con una somma inferiore o uguale a un numero fisso

Stavo cercando di risolvere Problema 279-B . Given an natural number, t, and an array, a[0],...,a[n-1], of natural numbers, find the maximum length of a continuous subarray, a[i],...,a[j] in a where a[i]+...+a[j] <= t. e.g. a=[3,1,2,1]...
posta 30.05.2016 - 15:26
1
risposta

perché l'aggiunta di un vertice in un grafico rappresentato utilizzando una matrice di adiacenza richiede O (| v | ^ 2) complessità temporale?

L'aggiunta di un vertice in un grafico rappresentato utilizzando una matrice di adiacenza richiede O (| v | ^ 2) complessità temporale in base al link ( operazione grafica > matrice di adiacenza > aggiungi vertice). Ma non sono riusci...
posta 20.09.2015 - 14:10
3
risposte

domande su un particolare algoritmo

Dopo aver cercato un algoritmo di primr veloce, mi sono imbattuto in questo: public static boolean isP(long n) { if (n==2 || n==3) return true; if ((n&0x1)==0 || n%3==0 || n<2) return false; long root=(long)Math.sqrt(n)+1...
posta 07.06.2012 - 09:01
1
risposta

Che cosa è esattamente la notazione "big O"? [duplicare]

Da quello che ho raccolto, la notazione O è usata per descrivere la lunghezza di un'operazione. Tuttavia, questo è quanto ho ottenuto. Che cosa è esattamente la notazione O e come sono i più comuni ( O(n) , O(2n) , O(n^2) , O...
posta 05.07.2013 - 05:22
1
risposta

Big-O per alberi immutabili

Come calcoli la complessità di tempo e spazio per un algoritmo ad albero che crea una copia di un albero, ma riutilizza il più possibile l'albero originale? Ad esempio, A /|\ B C G /|\ D E F Per cambiare E, possiamo adottare un...
posta 04.09.2015 - 22:09
1
risposta

Qual è la complessità temporale di questo programma?

Viene fornito un algoritmo su GeeksForGeeks.com per la costruzione di un albero di ricerca binario dal suo preorder traversal. Dicono che la complessità temporale per il codice seguente è O (n ^ 2). Ma secondo me dovrebbe essere O (nlogn)....
posta 23.07.2015 - 23:51
2
risposte

Big O Nested For Loop Breakdown

Capisco come ottenere un'immagine generale della grande O di un ciclo annidato, ma quali sarebbero le operazioni per ogni ciclo in un ciclo annidato per? Se abbiamo: for(int i=0; i<n; i++) { for(int j=i+1; j<1000; j++) {...
posta 30.09.2015 - 01:24
2
risposte

O (n ^ 2 * 2 ^ (log n)) == O (n ^ 2)

O(n^2 * 2^(log n)) == O(n^2) ? Perché penso che questo potrebbe essere il caso: Nel grande O, prendi solo le parti del termine che sono più rilevanti, giusto? %codice%. Il O(n^2 + 3n + 9) == O(n^2) ha un'influenza molto maggiore su...
posta 11.05.2016 - 15:03
6
risposte

Perché la definizione formale di notazione Big O è formulata come tale?

Considera la definizione formale: f(n) = O(g(n)) Perché non lo è: f(n) = O(f(n)) o f(n) = O(c*f(n)) dato che per l'analisi Big O, f(n)=2n e g(n)=n sono identici? Sono confuso dalla funzione f(n) che u...
posta 02.10.2011 - 11:25