Complessità algoritmo

di
Pr0gMa
il
3 risposte
P
Pr0gMa
Pochi posts
Iscritto da
nov, 2011
Messaggi:
20

Complessità algoritmo

Salve, mi stavo chiedendo quale fosse la complessità al caso peggiore di un algoritmo del tipo
while(i != n)
    n = numero casuale;
essendo i un numero prestabilito ed n generato con opportune funzioni. La risposta che mi viene spontanea è che la complessità sia infinita, è effettivamente così? Scusate la stupidità della domanda, sto approcciando l'argomento per la prima volta.

Grazie per l'attenzione!

3 Risposte

  • S
    Samuele
    Pochi posts
    Iscritto da
    lug, 2012
    Messaggi:
    14

    Re: Complessità algoritmo

    n = numero casuale;
    non è un'istruzione valida in c, a quanto mi riusulta. Se con esso intendi qualcosa tipo rand() allora se ne può discutere.
    In questo caso, comunque, credo non sia nemmeno possibile parlare di complessità, perché nulla ci assicura la terminazione del programma in qualche intervallo di tempo definito.
  • S
    smalldragon
    Molto attivo
    Iscritto da
    nov, 2008
    Messaggi:
    895

    Re: Complessità algoritmo

    In teoria la complessita rasenta l'infinito ci si avvicina ma non lo raggiunge mai visto che una botta di c... può sempre capitare.
    ma nella pratica invece no non appena il computer si scoccia, cioè capisce che sta perdendo tempo te lo blocca e lo termina.
    in questo caso non ti so dire quanto ci mette perchè non conosco gli algoritmi di ridondanza che utilizza windows.
  • S
    Samuele
    Pochi posts
    Iscritto da
    lug, 2012
    Messaggi:
    14

    Re: Complessità algoritmo

    Quando si prendono in considerazioni le complessità degli algoritmi, si devono utilizzare funzioni matematiche, come p. es. n, n^2, log(n)... Non puoi dire, per esempio, quale sia la complessità di un programma che entra in un loop infinito: semplicemente il programma non funziona. O se, ancora un altro esempio, la memoria va in overflow, sicuramente windows ti avvisa e blocca tutto, ma questo è indipendente dalla complessità dell'algoritmo che hai usato.
    E in ogni caso la complessità di un programma non può certo dipendere dal sistema operativo sotto il quale lo fai girare.
Devi accedere o registrarti per scrivere nel forum
3 risposte