Complessità algoritmo ricerca minimo

di il
7 risposte

Complessità algoritmo ricerca minimo

Salve, mi è stato posto come quesito il calcolo della complessità temporale nel caso medio, peggiore e migliore della ricerca del valore minimo all'interno di un vettore. 

Secondo me la complessità media, peggiore e migliore è sempre O(n) perchè per trovare il minimo è sempre necessario scansionare tutto il vettore.

E' corretto il mio ragionamento o sbaglio?

7 Risposte

  • Re: Complessità algoritmo ricerca minimo

    Possibile che non ti sia stato fornito una dispensa o un libro su cui studiare?

    Se si, che cosa?

    Se no, perche'?

    In ogni caso, il tuo ragionamento e' “sbagliato”.

  • Re: Complessità algoritmo ricerca minimo

    Ok grazie, ma il calcolo che dovrò fare non è uguale in tutti e tre i casi?

  • Re: Complessità algoritmo ricerca minimo

    Capisco che fare una ricerca sulla rete possa essere difficile e sia meno faticoso chiedere la "pappa pronta" su un forum, ma il primo risultato che ho trovato spiega tutto ciò che serve sulla ricerca di un elemento. Lo puoi adattare al tuo caso. Per risparmiarti la ricerca, ecco il link:

    https://italiancoders.it/ricerca-un-elemento-un-array/

  • Re: Complessità algoritmo ricerca minimo

    Che c'entra con il C?

    In ogni caso dipende dall'algoritmo e da cosa stai scansionando.

    Se, ad esempio,  è un array di unsigned int e a ogni passaggio controlli che sia uscito lo zero, il best case sarà evidentemente O(1)

  • Re: Complessità algoritmo ricerca minimo

    Ziovini, ‘fermate i manzi’ ;-)

    Non diciamo ‘sciocchezzuole’ ;-)

    Non centra niente il tipo di dato usato. Anche se fosse un array di uint, da nessuna parte c'e' scritto che il valore piu' piccolo sia uno zero.

    La questione e' piu' “subdola”: l'array e' ordinato?

    Lo dovrebbe fare l'autore del post, ma visto che ‘studiare e’ fatica, la fatica fa venire il mal di schiena e il mal di schiena fa morie', la risposta e':

    O(1) se l'array e' ordinato

    O(n) se si usa una banale scansione sequenziale

    O(infinity) se si usa il ‘bogus search’: genero un indice a caso e controllo se ho trovato il minimo, e continuo fino a quando non ho provato tutti gli indici, il che potrebbe richiedere un numero arbitrariamente alto di tentativi.

    Tutta robbbba che si trova su QUALUNQUE LIBRO di algoritmi, nei capitoli INIZIALI.

  • Re: Complessità algoritmo ricerca minimo

    @euscar

    La ricerca di un elemento è diversa dalla ricerca del minimo.

    Se usa l'algoritmo più intuitivo per la ricerca del minimo, avrà O(n) in tutti e tre i casi, ma non è così per tutti gli algoritmi 

  • Re: Complessità algoritmo ricerca minimo

    @migliorabile

    L'array ordinato fa parte del “dipende da cosa stai scansionando”

    Se fai il confronto con lo zero in un array non ordinato di valori senza segno (ma puoi fare un ragionamento analogo anche per i valori con il segno), il best case sarà O(1) per ogni array che avrà lo zero all'inizio (niente è minore del minimo assoluto). 

Devi accedere o registrarti per scrivere nel forum
7 risposte