Perchè Big O è insegnato invece di Big Theta?

20

La notazione Big O fornisce un limite superiore a una funzione, mentre Big Theta fornisce uno stretto legame. Tuttavia, trovo che la notazione di Big O sia tipicamente (e informalmente) insegnata e utilizzata quando in realtà significa "Big Theta".

es. "Quicksort is O (N ^ 2)" può diventare l'affermazione molto più strong "Quicksort is Θ (N ^ 2)"

Mentre l'uso di Big O è tecnicamente corretto, un uso più diffuso di Big Theta non sarebbe più espressivo e porterebbe a una minore confusione? C'è qualche ragione storica per cui questo Big O è più comunemente usato?

Wikipedia note:

Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe an asymptotic tight bound where using Big Theta Θ notation might be more factually appropriate in a given context.

    
posta tskuzzy 08.08.2011 - 13:57
fonte

2 risposte

26

Perché di solito ti interessa solo il caso peggiore quando analizzi la performance. Quindi, conoscere il limite superiore è sufficiente.

Quando viene eseguito più velocemente del previsto per un dato input, va bene, non è il punto critico. Sono informazioni per lo più trascurabili.

Alcuni algoritmi, come notato da @Peter Taylor, non hanno affatto un limite stretto. Vedi quicksort ad esempio che è O (n ^ 2) e Omega (n).

Inoltre, i limiti stretti sono spesso più difficili da calcolare.

Vedi anche:

risposta data 08.08.2011 - 14:00
fonte
9

Una ragione è che ci sono molti casi in cui Θ non è noto. Ad esempio, la moltiplicazione Matrix è O (n ^ 2.376) ma non esiste un limite stretto noto. Certo, per quanto posso dire, è un limite stretto per la moltiplicazione Matrix, ma non ne conosciamo il valore.

    
risposta data 08.08.2011 - 14:37
fonte

Leggi altre domande sui tag