COMPLEXITY_TRUE

-- COMPLESSITA' --

LISTE.C

List_Clear
{
    tempo:
    L'algoritmo cancella ricorsivamente una lista concatenata, per cui la complessità temporale dipende da quanti nodi ci sono arrivando fino a O(n)
    con n = numero di nodi.
    spazio:
    L'algoritmo cancella ricorsivamente una lista concatenata, per cui la complessità spaziale dipende da quanti nodi si devono cancellare
    arrivando fino a O(n), con n = numero di nodi.
}

List_Print2
{
    tempo:
    L'algoritmo stampa una lista concatenata in maniera ricorsiva per cui la complessità temporale è O(n) con n = numero di elementi nella lista.
    spazio:
    La complessità spaziale dipende dal numero di elementi nella lista puntata da 'head' per cui assume il valore asintotico di O(n).
}

List_Print
{
    tempo:
    L'algoritmo stampa una lista concatenata in maniera ricorsiva per cui la complessità temporale è O(n) con n = numero di elementi nella lista.
    spazio:
    La complessità spaziale dipende dal numero di elementi nella lista puntata da 'head' per cui assume il valore asintotico di O(n).
}

List_InsCoda
{
    tempo:
    L'algoritmo inserisce in coda un elemento in una lista concatenata, per cui la complessità temporale dipende da quanti nodi ci sono arrivando fino a O(n)
    con n = numero di nodi.
    spazio:
    L'algoritmo inserisce in coda un elemento in una lista concatenata, per cui la complessità spaziale dipende da quanti nodi bisogna scorrere
    per arrivare alla fine arrivando fino a O(n), con n = numero di nodi.
}

List_RemoveElem2
{
    tempo:
    L'algoritmo rimuove dalla coda un elemento in una lista concatenata, per cui la complessità temporale dipende da quanti nodi ci sono arrivando fino a O(n)
    con n = numero di nodi.
    spazio:
    La complessità di spazio si basa sulla dimensione della lista per cui è O(n).
}

List_RemoveElem
{
    tempo:
    L'algoritmo rimuove un elemento dalla coda di una lista concatenata in maniera ricorsiva per cui la complessità temporale è O(n) con n = numero
    di elementi nella lista.
    spazio:
    La complessità spaziale dipende dal numero di elementi nella lista puntata da 'head' per cui assume il valore asintotico di O(n).
}

FUN.C

choice
{
    tempo:
    L'algoritmo prende in input un numero controllando che non ci siano errori come l'input di un carattere.
    La complessità è costante (O(1)).
    spazio:
    L'algoritmo prende in input un numero controllando che non ci siano errori come l'input di un carattere, per cui non vengono allocate o create
    strutture dati aggiuntive.
    La complessità è costante (O(1)).
}

add_head
{
    tempo:
    L'algoritmo aggiunge in testa alla struttura dati puntata da 'minimo' un nuovo elemento.
    Questo accade in tempo costante (O(1)).
    spazio:
    L'algoritmo aggiunge in testa alla struttura dati puntata da 'minimo' un nuovo elemento.
    La complessità di spazio tende ad O(1) poichè incrementa semplicemente di 1 la dimensione precedente della struttura puntata da 'minimo'.
}

print_djkstra_path
{
    tempo:
    L'algoritmo stampa in modo ricorsivo la lista puntata da 'head' costruita con la funzione di Dijkstra.
    Il tempo di esecuzione dipende da quanti elementi ci sono per cui si arriva asintoticamente alla complessità di O(n) con n = numero elementi.
    spazio:
    Con questa funzione non vengono allocate o create nuove strutture dati per cui la complessità dipende dal numero di elementi nella lista puntata
    dalla variabile 'head' passata come parametro alla funzione e cioè è O(n).
}

Node_Cost
{
    tempo:
    L'algoritmo calcola semplicemente il costo in base al tipo di mezzo di trasporto passato come valore del parametro 'tipo'.
    Tutto ciò avviene in tempo costante O(1).
    spazio:
    Nell'algoritmo non vengono allocate nuove strutture dati. La complessità spaziale è costante O(1).
}

Node_Eff
{
    tempo:
    L'algoritmo calcola semplicemente l'efficienza in base al tipo di mezzo di trasporto passato come valore del parametro 'tipo'.
    Tutto ciò avviene in tempo costante O(1).
    spazio:
    Nell'algoritmo non vengono allocate nuove strutture dati. La complessità spaziale è costante O(1).
}

find_str
{
    tempo:
    L'algoritmo trova nell'array dei vertici una stringa confrontandola con la variabile 'ID' passata come parametro alla funzione.
    La complessità arriva ad un massimo di O(n) se si deve scorrere tutto l'array composto da n vertici.
    spazio:
    Non vengono create nuove strutture per cui la complessità si basa sulla dimensione di GR1 (che è un grafo) arrivando a O(|V| + |E|) con |V| = numero
    vertici e |E| = numero archi.
}

init_file
{
    tempo:
    L'algoritmo crea un grafo leggendo da un file tutti i dati utili.
    La complessità temporale dipende da quando si raggiunge la fine del file, ma poichè i dati letti sono in gruppi di 4 (in fscanf ci sono
    part, arr, tipo e dist), si arriva asintoticamente ad una complessità di 4*O(n) con n = numero archi creati in base ai dati letti.
    spazio:
    La complessità spaziale dipende da quanti archi vengono creati nell'algoritmo in base alla lettura di dati dal file di testo.
    Per cui si arriva asintoticamente ad O(|V| + |E|) con |V| = numero di vertici e |E| = numero di archi creati.
}

Graph_Menu
{
    tempo:
    La funzione inizia con la chiamata della funzione Graph_Create (complessità O(1)), poi c'è la funzione leggi (complessità O(|V|)) e poi c'è la funzione
    init_file (complessità O(|E|)).
    Subito dopo c'è un'istruzione switch case che è fatta per valutare 10 casi distinti.
    Caso 1:
    c'è la funzione Graph_Print; complessità caso 1: O(|V|*|E|);
    Caso 2:
    c'è la funzione Graph_Edge_ADD_IN; complessità caso 2: O(|V|);
    Caso 3:
    c'è la funzione Graph_Edge_Remove; complessità caso 3: O(|V|+|E|);
    Caso 4:
    ci sono la funzione Graph_Destroy (complessità O(|V|*|E|) e la funzione Graph_Create (complessità O(1)); complessità caso 4: O(|V|*|E|);
    Caso 5:
    c'è la funzione Graph_NodeAdd; complessità caso 5: O(|V|);
    Caso 6:
    c'è la funzione Graph_NodeRemove; complessità caso 6: O(|V|*|E|);
    Caso 7:
    c'è la funzione Graph_Random; complessità caso 7: O(|V|*log|V|);
    Caso 8:
    c'è la funzione dfs; complessità caso 8: O(|V|+|E|);
    Caso 9:
    il caso 9 si articola così:
    - ci sono alcune istruzioni if (complessità O(1));
    - c'è la funzione choice (complessità O(1));
    - c'è un'altra funzione choice (complessità O(1));
    - c'è un ciclo for sul numero di vertici del grafo (complessità O(|V|));
    - c'è un altro ciclo for sul numero di vertici del grafo in cui viene chiamata la funzione find_str (complessità totale O(|V|^2));
    - c'è la terza funzione choice (complessità O(1));
    - c'è la funzione Graph_Print (complessità O(|V|*|E|));
    - c'è la funzione choice (complessità O(1));
    - c'è un ciclo for che itera sul numero dei vertici e al cui interno si svolgono delle find_str, una List_Print2, una choice, una List_RemoveElem2
    ed un ciclo while sul numero degli archi (complessità totale ciclo for: O(|V|*(|V|+|E|)) = O(|V|^2));
    - c'è la funzione djkstra (complessità O(|V|) * O(|V|+|E|) = O(|V| * (|V|+|E|)) = O(|V|^2));
    - c'è la funzione print_djkstra_path (complessità O(|V|));
    - c'è un ciclo for sul numero dei vertici (complessità O(|V|));
    - c'è un ciclo for sul numero dei vertici in cui si svolge un ciclo while sul numero degli archi (complessità O(|V|*|E|));
    complessità caso 9: O((|V|^2)+ (|V|*|E|)).
    Alla fine di tutto, fuori dallo switch case c'è la funzione Graph_Destroy (complessità O(|V|*|E|)).
    Nel caso peggiore (se si sceglie sempre l'opzione 9) la complessità di tempo di tutto l'algoritmo arriva a O((|V|^2)+ (|V|*|E|)) = O(|V|^2).
    spazio:
    In tutto l'algoritmo viene creato ed usato un grafo (complessità O(|V| + |E|)) ed eventualmente una lista rappresentante il percorso minimo sul grafo
    generato nel caso 9 con la funzione djkstra (complessità di spazio della lista O(|V|)). La complessità di spazio totale è O(|V|+|E|).
}

all_visited
{
    tempo:
    L'algoritmo scorre la lista delle etichette puntata dalla variabile 'insieme' e itera finchè non trova un nodo con il campo 'visitato' pari a 0, arrivando
    ad una complessità nel caso peggiore O(n) con n = nodi letti iterativamente nel ciclo for.
    spazio:
    Non vengono allocate strutture aggiuntive per cui la complessità spaziale è O(n) con n = numero nodi della struttura puntata da 'etichette'.
}

leggi
{
    tempo:
    L'algoritmo legge da un file di testo le stringhe corrispondenti alle città della mappa rappresentata dal grafo GR1.
    A parte le istruzioni semplici che danno un contributo O(1) alla complessità temporale, vengono eseguiti due cicli for non innestati fra loro che
    agiscono per massimo n iterazioni, con n = numero vertici del grafo; per cui la complessità totale è O(n).
    spazio:
    La complessità spaziale dipende dalla grandezza del grafo per cui è O(|V| + |E|) con |V| = numero vertici, |E| = numero archi.
}

GRAPH.C

Graph_Create
{
    tempo:
    L'algoritmo crea un nuovo grafo vuoto, cioè con dei vertici non collegati tra loro.
    Ci sono tutte istruzioni semplici per cui la complessità temporale è costante O(1).
    spazio:
    La complessità spaziale è in relazione con il numero di vertici del grafo nuovo creato per cui si arriva asintoticamente a O(|V|), con |V| = numero vertici
    del grafo.
}

Graph_Destroy
{
    tempo:
    L'algoritmo dealloca un grafo iterando sull'array di vertici in un ciclo for (complessità O(|V|) con |V| = numero vertici) e iterando poi sulle
    liste di adiacenza relative ad ogni vertice (complessità O(|E|) con |E| = numero archi), per cui la complessità di tempo totale è O(|V|*|E|).
    spazio:
    La grandezza del grafo corrisponde alla somma del numero di vertici con il numero di archi per cui la complessità spaziale è di O(|V|+|E|).
}

Graph_Print
{
    tempo:
    L'algoritmo itera sull'array dei vertici e poi sulle adiacenze corrispondenti ad ogni vertice del grafo per cui la complessità spaziale arriva a
    O(|V|*|E|) con |V| = numero vertici, |E| = numero archi.
    spazio:
    L'algoritmo sfrutta la struttura dati di un grafo con i suoi vertici e i suoi archi rappresentati con le liste di adiacenza per cui la complessità
    spaziale corrisponde a O(|V|+|E|).
}

Graph_Edge_ADD_IN
{
    tempo:
    L'algoritmo consiste di istruzioni semplici con in più delle istruzioni condizionali che danno un contributo di O(1) alla complessità, delle chiamate
    alla funzione find_str che dà un contributo O(|V|) con |V| = numero vertici del grafo, una chiamata alla funzione Graph_Edge_ADD che ha complessità
    O(1) e delle chiamate alla funzione choice che ha complessità O(1). Per cui la complessità di tempo totale è O(|V|) + O(1) = O(|V|).
    spazio:
    Viene usato un grafo per cui la complessità asintotica di spazio assume il valore di O(|V|+|E|).
}

Graph_Edge_ADD
{
    tempo:
    L'algoritmo aggiunge un nuovo arco nel grafo con istruzioni semplici, tranne quando si richiamano le funzioni Node_Eff e Node_Cost che danno comunque
    un contributo di O(1) alla complessità totale dell'algoritmo; per cui la complessità di tempo arriva a O(1).
    spazio:
    La complessità di spazio dell'algoritmo si basa sulla grandezza della struttura dati del grafo per cui è O(|V|+|E|) con |V| = numero vertici,
    |E| = numero archi.
}

Graph_Edge_Remove
{
    tempo:
    Nell'algoritmo ci sono delle istruzioni condizionali non annidate che hanno complessità O(1), delle chiamate alla funzione find_str che ha complessità
    O(|V|) con |V| = numero vertici del grafo, una chiamata alla funzione List_Print2 che ha complessità O(|E|) con |E| = numero archi del grafo, una
    chiamata alla funzione choice che ha complessità O(1) ed un ciclo while che scorre gli archi uscenti da un vertice particolare (complessità O(|E|))
    Per cui la complessità temporale totale è di O(|V|+|E|).
    spazio:
    Viene usato un grafo per cui la complessità spaziale asintotica è di O(|V|+|E|).
}

Graph_NodeAdd
{
    tempo:
    Nell'algoritmo c'è una chiamata alla funzione find_str per vedere se il nodo nuovo non sia già presente nel grafo (complessità O(|V|)), un ciclo for
    che itera sul numero dei vertici ed in cui si eseguono operazioni elementari (complessità ciclo for O(|V|)), e infine se viene valutata vera una certa
    condizione, oltre a delle operazioni elementari viene chiamata la funzione re_ID (complessità O(|V|)).
    La complessità totale di tempo arriva dunque ad un valore asintotico di O(|V|) dove |V| è il numero di vertici del grafo.
    spazio:
    Nella funzione si usa un grafo per cui la complessità di spazio corrisponde ad O(|V|+|E|) con |E| = numero di archi del grafo.
}

Graph_NodeRemove
{
    tempo:
    Nell'algoritmo c'è una chiamata alla funzione find_str (complessità O(|V|), una chiamata alla funzione List_Clear (complessità O(|E|)) ed un ciclo
    for che itera sul numero di vertici |V| del grafo chiamando a sua volta la funzione List_RemoveElem (complessità O(|E|)).
    La complessità di tempo raggiunge il valore asintotico di O(|V|+|E|) + O(|V|*|E|) = O(|V|*|E|) con |E| = numero di archi del grafo.
    spazio:
    Viene usato un grafo per cui la complessità di spazio corrisponde alla sua grandezza e cioè ad O(|V|+|E|).
}

Graph_Random
{
    tempo:
    Nell'algoritmo ci sono 2 cicli for, uno innestato nell'altro: quello interno itera sul logaritmo in base 2 del numero di vertici, richiamando
    la funzione Graph_Edge_ADD che ha complessità O(1), dando al ciclo interno una complessità di O(log|V|); il ciclo esterno invece itera sul numero di
    vertici effettivo per cui la complessità di tempo totale dell'algoritmo è O(|V|*log|V|) con |V| = numero vertici del grafo.
    spazio:
    Viene usato nell'algoritmo un grafo con liste di adiacenza per cui la complessità di spazio corrisponde ad O(|V|+|E|) dove |E| = numero archi del grafo.
}

dfs1
{
    tempo:
    L'algoritmo è richiamato ricorsivamente su ogni nodo del grafo per cui la complessità di tempo dell'algoritmo dipende da quanti archi possiede un nodo
    e cioè è O(|E|) con |E| = numero archi di un vertice.
    spazio:
    L'algoritmo prende in input un grafo per cui la complessità spaziale corrisponde ad O(|V|+|E|) con |V| = numero vertici del grafo.
}

dfs
{
    tempo:
    Nell'algoritmo c'è un ciclo for che itera sul numero di vertici presenti nel grafo e contemporaneamente chiama la funzione dfs1 che dà contributo
    O(|E|) alla complessità dell'algoritmo che arriva ad avere così una complessità temporale totale di O(|V|+|E|) con |V| = numero vertici,
    |E| = numero archi.
    spazio:
    Viene usato un grafo per cui la complessità di spazio è O(|V|+|E|).
}

re_ID
{
    tempo:
    Nell'algoritmo oltre alle istruzioni semplici che danno contributo O(1) alla complessità temporale, c'è un ciclo for che itera sul numero di
    vertici del grafo, per cui la complessità asintotica di tempo effettiva è O(|V|) dove |V| è proprio il numero di vertici presenti.
    spazio:
    Viene usato un grafo con i suoi |V| vertici e i suoi |E| archi per cui la complessità spaziale corrisponde ad O(|V|+|E|).
}

relaxDist
{
    tempo:
    L'algoritmo esegue delle operazioni aritmetiche singole in base alla verifica di una condizione in un'espressione condizionale, per cui
    la complessità di tempo è costante (cioè O(1)).
    spazio:
    Nell'algoritmo vengono impiegati un grafo e una lista di etichette per cui la complessità di spazio corrisponde a O(|V| + |E|)
    con |V| = numero vertici, |E| = numero archi.
}

relaxCost
{
    tempo:
    L'algoritmo esegue delle operazioni aritmetiche singole in base alla verifica di una condizione in un'espressione condizionale, per cui
    la complessità di tempo è costante (cioè O(1)).
    spazio:
    Nell'algoritmo vengono impiegati un grafo e una lista di etichette per cui la complessità di spazio corrisponde a O(|V| + |E|)
    con |V| = numero vertici, |E| = numero archi.
}

relaxEff
{
    tempo:
    L'algoritmo esegue delle operazioni aritmetiche singole in base alla verifica di una condizione in un'espressione condizionale, per cui
    la complessità di tempo è costante (cioè O(1)).
    spazio:
    Nell'algoritmo vengono impiegati un grafo e una lista di etichette per cui la complessità di spazio corrisponde a O(|V| + |E|)
    con |V| = numero vertici, |E| = numero archi.
}

get_min
{
    tempo:
    L'algoritmo esegue un ciclo su un array di struct ed esegue delle singole operazioni in seguito al verificarsi di alcune condizioni;
    per cui la complessità asintotica di tempo corrisponde a O(n) con n = grandezza array di etichette.
    spazio:
    Viene impiegato un array di struct per cui la complessità di spazio corrisponde ad O(n) con n = grandezza array di etichette.
}

calcPeso
{
    tempo:
    Nell'algoritmo c'è un ciclo while che itera sulla lista di adiacenze del nodo di partenza che serve per trovare l'arco corrispondente con il vertice
    'dest' passato alla funzione per poi ritornare l'eventuale distanza se c'è. La complessità di tempo nel caso peggiore è O(|E|) con |E| = numero archi.
    spazio:
    Nell'algoritmo si usa un grafo per cui la complessità spaziale corrisponde alla sua grandezza e cioè O(|V| + |E|) dove |V| è il numero di vertici presenti.
}

djkstra
{
    tempo:
    Nell'algoritmo vengono eseguiti:
    - un ciclo for sul numero dei vertici del grafo (complessità O(|V|));
    - un ciclo while sul numero dei nodi del grafo (complessità O(|V|)) ed al suo interno:
    - - una chiamata alla funzione get_min (complessità O(|V|));
    - - un ciclo while sul numero di archi di un nodo che vengono impiegati per la chiamata alla funzione relaxCost,relaxDist,relaxEff (complessità totale O(|E|));
    che danno al ciclo while la complessità totale di O(|V|*((V)+(E)));
    - un ciclo while che nel caso peggiore itera su tutti i nodi del grafo (complessità O(|V|)).
    La complessità totale dell'algoritmo in termini di tempo è di O(|V|) + O(|V|)*O(|V|+|E|) + O(|V|) = O(|V|) * O(|V|+|E|).
    spazio:
    Nell'algoritmo viene usato un grafo (complessità O(|V|+|E|)) e viene creata una lista concatenata che rappresenta il percorso minimo tra i vertici
    del grafo (complessità O(|V|)) per cui la complessità spaziale asintotica arriva ad un valore di O(|V|+|E|).
}

MAIN.C


main
{
    tempo:
    C'è la funzione Graph_Menu che ha una complessità di tempo nel caso peggiore di O(|V|^2) dove |V| è il numero di vertici del grafo.
    spazio:
    Come nella funzione Graph_Menu, si usa un grafo e si crea la lista rappresentante il percorso minimo di djkstra, ottenendo così la complessità
    di spazio di O(|V|+|E|).
}