Domande con tag 'big-o'

domande con tag
11
risposte

Ottieni 100 numeri più alti da una lista infinita

A una mia amica è stata posta questa domanda dell'intervista - "There is a constant flow of numbers coming in from some infinite list of numbers out of which you need to maintain a datastructure as to return the top 100 highest numbers...
posta 26.10.2011 - 09:59
20
risposte

Esistono algoritmi del mondo reale che sovraperformano notevolmente nella classe sottostante? [chiuso]

La scorsa notte stavo discutendo con un altro programmatore che anche se qualcosa potrebbe essere O (1), un'operazione che è O (n) potrebbe sovraperformare se c'è una grande costante nell'algoritmo O (1). Era in disaccordo, quindi l'ho portato q...
posta 07.10.2011 - 19:31
5
risposte

Si tratta di una "Regola" corretta per l'identificazione della notazione "Big O" di un algoritmo?

Ho imparato di più su Big O Notation e su come calcolarlo in base a come viene scritto un algoritmo. Mi sono imbattuto in un interessante insieme di "regole" per il calcolo di un algoritmo di notazione Big O e volevo vedere se sono sulla strada...
posta 09.04.2013 - 15:51
5
risposte

Determinare se un Algoritmo è O (log n)

Sto aggiornando la mia teoria di CS, e voglio sapere come identificare l'algoritmo O (log n) complessità. In particolare, esiste un modo semplice per identificarlo? Conosco O (n), di solito hai un ciclo singolo; O (n ^ 2) è un doppio ciclo; O...
posta 26.04.2012 - 02:46
2
risposte

Algoritmo per unire due array ordinati con un numero minimo di confronti

Sono presenti due array ordinati a , b di tipo T con dimensioni n e m . Sto cercando un algoritmo che unisce i due array in un nuovo array (di dimensione massima n + m). Se si dispone di un'operazione di confronto a basso costo, quest...
posta 26.12.2014 - 13:15
4
risposte

Quando parlo, come posso dire che l'ordine di complessità temporale di un algoritmo è O (N log N)?

Che termine posso usare per descrivere qualcosa con complessità di O (N log N)? Ad esempio: O (1): costante O (log N): logaritmico O (N): lineare O (N log N): ?????? O (N 2 ): Quadratico O (N 3 ): Cubico
posta 18.07.2015 - 09:01
5
risposte

Algoritmi: come riassumo O (n) e O (nlog (n)) insieme?

Ho il seguente algoritmo che trova i duplicati e li rimuove: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) {...
posta 08.10.2014 - 22:59
7
risposte

Cos'è O in Big O?

Che cos'è Big e O nella notazione Big O? Ho letto le definizioni e non dice cosa sia O pronunciato come 'oh'. Ad esempio, capisco che O (n) è la complessità di un algoritmo lineare in cui n potrebbe essere il numero di operazioni. ma cos'è u...
posta 13.09.2011 - 20:03
6
risposte

Come si chiama quando si modifica il tempo di esecuzione Big O di una funzione [chiuso]

Diciamo che ho una funzione che ordina un database in O(n^2) di tempo. Voglio procedere al refactoring in modo che venga eseguito in O(n log(n)) di tempo, e così facendo cambierò il modo fondamentale di funzionamento dell'operazione, m...
posta 07.01.2018 - 15:23
4
risposte

Perché è mergesort O (log n)?

Mergesort è un algoritmo divide and conquer ed è O (log n) perché l'input è ripetutamente dimezzato. Ma non dovrebbe essere O (n) perché anche se l'input è dimezzato ogni ciclo, ogni elemento di input deve essere iterato per fare lo swapping in...
posta 13.09.2015 - 20:31