Limite inferiore e superiore di un algoritmo

Sono applicabili a tutti i casi, ma il "peggiore dei casi" è quello seguito dalla maggior parte dei programmatori perché è sempre meglio assumere il caso peggiore (quando si progettano algoritmi).

In generale, il limite inferiore è il migliore (minore quantità di lavoro eseguito) e il limite superiore è il caso peggiore (la maggior parte del lavoro che l'algoritmo dovrà fare). Il caso medio è un calcolo probabilistico tra limiti superiori e inferiori (il risultato non è necessariamente da qualche parte nel mezzo, poiché a volte il limite inferiore è potenzialmente raro - o quando la probabilità non è semplice da stabilire).

Questi limiti sono utili in genere perché restringono la tua considerazione a "nulla che io possa fare questo particolare algoritmo per esibirsi meglio di questo limite o peggio di questo". Quindi sì, saranno un tema ricorrente nei tuoi futuri endevours per capire gli algoritmi.

Vorrei solo notare che molti programmi si fermano alle considerazioni del caso peggiore, con una semplice salatura della discussione sul caso medio. Ciò non significa che tutte le persone in vari campi prendano in considerazione - sono solo tutte le classi di istruzione di livello più basso / i libri che si preoccupano di discutere.