Questa prima domanda affronta alcuni dei fattori che potrebbero causare un algoritmo con complessità O (log n). Cosa potrebbe causare ad un algoritmo una complessità temporale O (log log n)?
Ho visto questa domanda su Reddit e non sono state presentate soluzioni positive, e ho pensato che sarebbe stata una domanda perfetta da porre qui. Questo era in una discussione sulle domande dell’intervista: Scrivi un metodo che accetta un array int di dimensione m e restituisce (Vero / Falso) se la matrice è composta dai […]
Ho difficoltà a decidere quale sia la complessità temporale del più grande algoritmo del comune denominatore di Euclid. Questo algoritmo in pseudo-codice è: function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a Sembra dipendere da a e b . Il mio pensiero è che […]
Ho un numero variabile di ArrayList che ho bisogno di trovare l’intersezione di. Un limite realistico al numero di serie di stringhe è probabilmente intorno ai 35 ma potrebbe essere più. Non voglio alcun codice, solo idee su ciò che potrebbe essere efficiente. Ho un’implementazione che sto per iniziare a programmare ma voglio ascoltare altre […]
Sto lavorando al programma necessario solo nel seguito per capirlo meglio. Qual è il peggior caso di esecuzione di Quicksort e cosa potrebbe causare questa peggiore performance del caso? Come possiamo modificare il programma Quicksort per mitigare questo problema? So che ha il caso peggiore O(n^2) e so che si verifica quando l’elemento minimo o […]
Esiste un algoritmo che, dati due set, calcoli la loro intersezione in tempo lineare? Posso eseguire due cicli for per controllare tutte le coppie di elementi, registrando gli elementi che trovo in entrambi i set. Tuttavia, il tempo di esecuzione sarà O (n 2 ). Come faccio a farlo nel tempo O (n)?
Ci sono risorse sulla complessità asintotica (big-O e il resto) dei metodi delle classi di raccolta .NET ( Dictionary , List etc …)? So che la documentazione della libreria C5 include alcune informazioni a riguardo ( esempio ), ma mi interessano anche le raccolte .NET standard … (e anche le informazioni di PowerCollections sarebbero belle).
Sono confuso riguardo alla complessità temporale della tabella hash molti articoli affermano che sono “O (1)” ammortizzato non vero ordine O (1) che cosa significa in applicazioni reali. Qual è la complessità temporale media delle operazioni in una tabella hash, nell’attuazione reale non in teoria, e perché le operazioni non sono vere O (1)?
La mia conoscenza del big-O è limitata e quando i termini del registro vengono visualizzati nell’equazione, questo mi butta via ancora di più. Qualcuno può forse spiegarmi in termini semplici che cos’è un algoritmo O(log n) ? Da dove viene il logaritmo? Questo è emerso in particolare quando stavo cercando di risolvere questa domanda di […]
Sono interessato a creare una struttura dati Java simile a uno stack che supporta le seguenti operazioni nel modo più efficiente ansible: Push, che aggiunge un nuovo elemento in cima allo stack, Pop, che rimuove l’elemento superiore della pila, Find-Max, che restituisce (ma non rimuove) l’elemento più grande della pila, e Find-Min, che restituisce (ma […]