Notazione per la complessità temporale media di un algoritmo

1

Quale notazione usi per la media complessità temporale di un algoritmo? Mi viene in mente che il modo corretto sarebbe usare il big-theta per riferirsi a un insieme di risultati (anche quando una prova specifica può differire). Ad esempio, la ricerca media dell'array sarebbe Θ (n + 1) / 2.

È giusto?

Spiegazione del tempo di ricerca medio essendo Θ (n + 1) / 2: Dato che la somma del tempo di accesso per i primi n interi è n (n + 1) / 2, il tempo medio per un gran numero di accessi casuali a la matrice sarà (n (n + 1) / 2) / n = (n + 1) / 2. In questo caso, direi che Θ (n + 1) / 2 sarà il tempo di accesso medio. Ha senso (per me) ma poiché sono nuovo alla notazione asintotica (e alla programmazione in generale), mi piacerebbe sapere se questa è una pratica comune.

Te lo chiedo perché sono confuso nel vedere Big-O essere usato ovunque in pagine come link . es .: caso medio di ricerca di array O (n).

    
posta user2106285 11.05.2013 - 07:46
fonte

1 risposta

6
f ∈ Θ(g)

è uguale a

f ∈ Ο(g) ∧ f ∈ Ω(g)

Quindi, se puoi dimostrare che f ∈ Ο(g) ∧ f ∈ Ω(g) , allora usa assolutamente Θ .

Si noti che questo non ha assolutamente nulla a che fare con la complessità temporale degli algoritmi, nella media o in altro modo. Θ , Ο , ο , Ω e ω riguardano il tasso di crescita delle funzioni; se tali funzioni descrivono la complessità media temporale / passo / spazio di un algoritmo, la complessità caso / tempo / spazio di un algoritmo, la complessità caso / tempo / spazio di un algoritmo, la complessità caso / tempo / spazio previsto di un algoritmo, la popolazione della Cina, il numero di utenti su StackOverflow o le dimensioni del reggiseno di Lara Croft sono completamente irrilevanti.

    
risposta data 11.05.2013 - 17:01
fonte

Leggi altre domande sui tag