Migliore limite superiore e migliore limite inferiore di un algoritmo

Question

Migliore limite superiore e migliore limite inferiore di un algoritmo

#1 da (2 voti)

2

Sto studiando per un esame finale e ho superato una domanda che avevo su un test precedente.

Le domande ci chiedono di trovare il valore minimo in un array non ordinato di numeri interi. Dobbiamo fornire il miglior limite superiore e il miglior limite inferiore possibile per il problema nel peggiore dei casi.

Innanzitutto, in questo esempio, il limite superiore e inferiore sono uguali (quindi, possiamo parlare in termini di Big-Theta). Nel peggiore dei casi, dovremmo esaminare l'intera lista in quanto il valore minimo sarebbe alla fine della lista. Pertanto, la risposta è Big-Theta (n).

È corretto e amp; buona spiegazione?

algorithms complexity big-o

posta darksky 29.11.2011 - 02:12

fonte

1 risposta

Leggi altre domande sui tag algorithms complexity big-o

Sceglieresti un database o un dvcs come memoria per un wiki di documentazione? MVC Validazione con ModelState.isValid attraverso una procedura guidata

score 2 · Accepted Answer

In the worst case, we would have to go through the whole list as the minimum value would be at the end of the list.

Devi comunque passare in rassegna l'intera lista, perché altrimenti non sai se il minimo attuale sia effettivamente il minimo assoluto. Quindi l'algoritmo richiederebbe sempre iterazioni.

L'unica eccezione è se si conoscono limiti sui valori possibili, ad esempio che gli interi sono tutti positivi e si è già trovato un 1 (quindi è possibile interrompere). Ciò tuttavia non modifica la discussione sulla complessità.