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).