Big O VS Big $ \ Theta $ Durante il colloquio di codifica

Question

Quasi ogni volta che vedo un articolo sul tempo o sulla complessità spaziale, le persone stanno esprimendo la complessità con Big O, mentre dovrebbe essere $ \ theta $ . Dal libro "Cracking the coding intervista":

.

"Nell'industria (e quindi nelle interviste), le persone sembrano fondere θ e

Answer 1

Ecco una risposta da Reddit che ho trovato il più utile:

.

Immagino che diressi, se qualcuno dice: "Cosa c'è di o di inserimento?", vuoi dire "è $ o (n ^ 2) $ ".Certo non è precisamente la stessa cosa che dice che è " $ \ theta (n ^ 2) $ nel caso peggiore", ma è una convenzione che tutti capiscono, eCi vuole meno tempo per ottenere le parole fuori dalla bocca.

Answer 2

Penso che sia bene.Mostra solo l'intervistatore che in realtà sappia cos'è il vero significato di Big-O e Theta.Assicurati che sia effettivamente vero (la $ \ omega $ parte) quando si dispone di un algoritmo complicato e hai usato una certa disuguaglianza per la prova di complessità Big-O.

Answer 3

Se menzioni Big-Theta molti intervistatori penserà che ti sbagli perché non ne hanno mai sentito parlare.Se poi inizi a discuterlo, allora fallisci a ciò che il colloquio è principalmente su: convincere l'intervistatore che vogliono lavorare con te.

Domanda: controlli se x è un primario collaborando la divisione di 2, 3, 5, 7, 11 ecc. Qual è il Big-O della complessità del tempo?Se rispondi "è grande-theta", cosa sarà la mia opinione di te?