COMPLESSITA' SERVER

int main() {
    struct PC *client=situazione_iniziale();
    menu(client);
    printf("\n\n\t\t\tProgramma terminato.\n");
        system("PAUSE");
        return 0;
}

comp_0 MAIN:
{
	tempo:
	Si inizializza la variabile client con l'algoritmo situazione_iniziale (complessità O(m^2)) e si chiama la funzione menu (complessità MAX*O(m)).
	La complessità totale è perciò O(m^2).
	spazio:
	Si usa la lista di n pc aventi ognuna una lista di m jobs, occupando al massimo, in termini asintotici un O(n+m).
}


comp_1 INSORDINE:
{
	tempo:
	La complessità di tempo dipende dal numero di confronti da eseguire con gli elementi della lista esistente per inserire un nuovo elemento;
	si può andare da 0 confronti (lista vuota) a m confronti (l'elemento deve essere inserito alla fine), per cui essendo un algoritmo ricorsivo
	la complessità di tempo si riduce a O(m).
	spazio:
	L'algoritmo sfrutta la struttura dati di una lista concatenata, contenente i valori da confrontare con l'elemento da inserire in modo ordinato;
	per cui la complessità di spazio è O(m).
}


comp_2 STAMPA:
{
	tempo:
	Si scorre la lista di n pc applicando l'algoritmo insStampa (complessità O(m)) ottenendo la complessità O(n*m) mentre alla fine si usa la funzione
	stampaggio (complessità O(m)). La complessità temporale totale è O(m*n).
	spazio:
	Si usa una lista di n elementi da cui si diramano m altri elementi, il che occupa in tutto uno spazio massimo pari ad un O(n+m).
}


comp_3 INSSTAMPA:
{
	tempo:
	L'algoritmo inserisce nella coda elementi presenti nella lista di job di un pc evitando le ridondanze;
	se siamo all'inizio, la coda sarà vuota e quindi l'elemento non è già presente e sarà inserito, ma se non è vuota si scorre la lista
	costituita dalla coda finchè o non si trovano ridondanze, e quindi si inserisce l'elemento alla fine, oppure si continua a scorrere arrivando
	a non inserire l'elemento passato come parametro alla funzione.
	La complessità asintotica di tempo di questo algoritmo dipende da quanto confronti si eseguono, arrivando al massimo a m confronti
	(si scorre tutta la lista), per cui la complessità di tempo è data al massimo da O(m).
	spazio:
	L'algoritmo sfrutta la struttura dati di una lista concatenata, contenente i valori da confrontare con l'elemento da inserire;
	poichè essi sono al più m, la complessità di spazio è O(m).
}


comp_4 RANDOMIZE:
{
	tempo:
	All'inizio con un ciclo while si scorre la lista di pc per ricavare il numero esatto di pc incrementando la variabile 'i', iterando n volte
	(complessità O(n));
	subito dopo si fa un controllo sul valore effettivo di questa variabile per effettuare una operazione aritmetica il cui valore va assegnato
	alla variabile 'inserimento' (complessità O(1) sia che si entri nel ramo if che si entri nel ramo else);
	subito dopo si entra in un ciclo while durante il quale si eseguono: un ciclo for che dura 100/n iterazioni a causa degli n pc (complessità O(n)),
	vari assegnamenti e stampe (complessità O(1)), un ciclo for che viene usato per inserire in ordine dei job nella lista dei jobs di un pc
	(sfruttando la funzione insOrdine che ha complessità di tempo O(m) per m elementi da inserire) e altri assegnamenti (complessità O(1)); dopo
	queste operazioni nel while si ha la complessità O(m) + O(n) + 1 e poichè m rappresenta il numero di inserimenti possibili nella lista dei jobs di
	un pc e poichè essi sono in numero esponenzialmente maggiore rispetto ai pc, allora tutto si riduce a O(m), facendo assumere a tutto il while
	una complessità di tempo di O(m*n).
	In definitiva, tutto l'algoritmo ha una complessità di tempo asintotica di O(n) + O(1) + O(n*m) che si riduce ad O(n*m).
	spazio:
	Nell'algoritmo si usa una struttura dati che presenta una lista di n elementi (i pc) che hanno a loro volta un numero massimo di m elementi
	nella lista dei propri jobs, richiedendo uno spazio massimo che tende ad un O(n+m).
}


comp_5 STAMPAGGIO:
{
	tempo:
	L'algoritmo stampa in modo ricorsivo gli m jobs di uno specifico pc, arrivando ad ottenere una complessità asintotica di tempo di O(m).
	spazio:
	L'algoritmo manda in stampa m elementi occupando asintoticamente uno spazio di O(m).
}


comp_6 LISTA_PC:
{
	tempo:
	L'algoritmo stampa gli ID di n pc scorrendo ricorsivamente n elementi, ottenendo una complessità asintoticamente di O(n).
	spazio:
	L'algoritmo stampa gli ID di n pc scorrendo ricorsivamente n elementi, che avendo loro m jobs, occupano asintoticamente uno spazio massimo
	di O(n+m).
}


comp_7 CERCA_PC:
{
	tempo:
	L'algoritmo ricerca in una lista concatenata un elemento in base ad una chiave specifica; poichè ci sono n pc, asintoticamente la complessità
	arriva a O(n).
	spazio:
	Data la conformazione della struttura usata, l'algoritmo occupa uno spazio di O(n+m).
}


comp_8 CAMBIO_PRIORITA:
{
	tempo:
	L'algoritmo ha lo scopo di cambiare la priorità di un pc cercandolo e spostandolo nella lista dei pc (se esso è presente).
	Prima usa un ciclo while per contare i pc (complessità O(n)), poi li si stampa per dare all'utente l'ordine di stampa prima del cambio priorità
	(complessità O(n)), poi si riusa l'algoritmo cerca_pc per capire se un certo pc esiste ed assegnare un valore ad una variabile (complessità totale
	O(n)), poi tramite il ramo if di un'istruzione if-else si eseguono varie volte algoritmi con complessità O(n) che non sono mai annidati fra loro,
	e poi si stampa la lista com'è diventata (complessità O(n)), altrimenti, si stampa il fatto che non è stato possibile trovare il pc voluto.
	In definitiva, si ha una complessità di tempo asintotica di O(n).
	spazio:
	Nell'algoritmo si usa una lista di n pc con m jobs ciascuno, così si ha una complessità di O(n+m).
}


comp_9 NUOVA_LISTA_PC:
{
	tempo:
	Con quest'algoritmo si crea una lista di n elementi (i pc) senza i relativi jobs, perciò si ha una complessità di O(n).
	spazio:
	Si crea una lista di n pc senza i relativi jobs, così la complessità spaziale asintotica è di O(n).
}


comp_10 PRINTALL:
{
	tempo:
	L'algoritmo scorre gli n pc per stampare gli m jobs che hanno, ottenendo una complessità di tempo totale di O(n*m).
	spazio:
	Si usa una lista di n elementi da cui si diramano m altri elementi, occupando uno spazio massimo di O(n+m).
}


comp_11 NUMERO_PC:
{
	tempo:
	L'algoritmo prende in input e lo restituisce il numero esatto di pc che poi sarà usato da altri algoritmi, ottenendo una complessità temporale
	asintotica di O(n), nel caso in cui si sbagli n volte l'inserimento del numero.
	spazio:
	La complessità spaziale dell'algoritmo è O(1) in quanto si acquisisce un semplice valore intero.
}


comp_12 DELETE_JOB:
{
	tempo:
	C'è un'istruzione if-else che controlla se ci sono dei pc; nel caso in cui ci siano, si usa un while per scorrere la lista degli n pc
	per trovare quello che ci serve (complessità O(n)).
	Nel caso in cui esista, si procede con un ciclo while per cercare il job nella lista di m jobs del pc trovato;
	nel caso che si trovi si eseguono i semplici assegnamenti che permettono la cancellazione di un elemento da una lista (complessità O(1)).
	In definitiva la complessità temporale asintotica dell'algoritmo è O(n+m).
	spazio:
	Poichè si usa una struttura di n pc con m jobs, la complessità spaziale è O(n+m).
}


comp_13 NEW_JOB:
{
	tempo:
	Nell'algoritmo si crea un semplice elemento, perciò la complessità è O(1).
	spazio:
	Per lo stesso motivo di prima, la complessità spaziale è O(1).
}


comp_14 INS_PC:
{
	tempo:
	Nell'algoritmo si crea la lista degli n pc, così si ha una complessità di O(n).
	spazio:
	Nell'algoritmo si usa una lista di n elementi, perciò si occupa asintoticamente uno spazio pari a un O(n).
}


comp_15 DUMP:
{
	tempo:
	Nell'algoritmo si scorre ricorsivamente la lista degli m jobs, conferendo all'algoritmo una complessità temporale di O(m).
	spazio:
	Nell'algoritmo si scorrono m elementi, perciò si occupa lo spazio di O(m).
}


comp_16 SHUTDOWN:
{
	tempo:
	Nell'algoritmo si scorrono gli n pc per usare l'algoritmo dump sui suoi m jobs (complessità O(m)), per cui la complessità massima di tempo è O(n+m).
	spazio:
	Nell'algoritmo si usa una struttura di n elementi da cui se ne diramano altri m, per cui si occupa lo spazio asintotico pari a O(n+m).
}


comp_17 CHOICE:
{
	tempo:
	La complessità è O(1).
	spazio:
	La complessità è O(1).
}


comp_18 SITUAZIONE:
{
	tempo:
	Nell'algoritmo di eseguono le seguenti operazioni:
	si crea una nuova lista di n pc (complessità O(n));
	si prende in input un numero (complessità O(1));
	se il numero è 1, si usa l'algoritmo randomize (complessità O(n*m));
	se il numero è 2, si prende in input un numero (complessità O(1)), si stampano i pc che si hanno (complessità O(n)), si prende in input
	l'id di un pc e lo si cerca (complessità O(n)); se il risultato della ricerca è sia 1 che 2 si usa l'algoritmo new_job per creare il singolo job
	(complessità O(1)) e poi si usa l'algoritmo insOrdine (complessità O(m)), il tutto in un ciclo while che itera per m volte (numero di jobs che si
	è scelto di creare), ottenendo in totale una complessità di O(m^2).
	In definitiva la complessità è di O(m^2).
	spazio:
	Si usa una lista di n elementi aventi a loro volta liste di m altri elementi, che occupano in totale in termini asintotici uno spazio pari a O(n+m).
}


comp_19 MENU:
{
	tempo:
	Nell'algoritmo si eseguono le seguenti operazioni:
	si prende in input un numero (complessità O(1));
	in base al numero inserito si attiva uno switch case.
	Caso 1:
	si prende in input un ID e si cerca se esiste già (complessità O(n)) in un do while, ottenendo una complessità O(n^2); alla fine lo si inserisce con l'algoritmo
	ins_pc (complessità O(n)). COMPLESSITA' CASO 1: O(n^2).
	Caso 2:
	si prende in input un id e lo si cerca (O(n^2) perchè potrebbe non essere inserito subito un numero giusto), e se esiste si crea un job e lo si inserisce
	nella lista dei job del pc trovato (complessità O(m)). COMPLESSITA' CASO 2: O(m) (m è un numero molto maggiore di n ed anche di n^2).
	Caso 3:
	si inseriscono il nome di un job e l'id di un pc e si usa l'algoritmo delete_job (complessità O(m)). COMPLESSITA' CASO 3: O(m).
	Caso 4:
	si usa semplicemente l'algoritmo di printALL (complessità O(n*m). COMPLESSITA' CASO 4: O(n*m).
	Caso 5:
	si usa l'algoritmo stampa (complessità O()) e si usa l'algoritmo shutdown (complessità O(n+m)). COMPLESSITA' CASO 5:
	Caso 6:
	si usa l'algoritmo cambio_priorita (complessità O(n)). COMPLESSITA' CASO 6: O(n).
	La complessità di tutto lo switch case, asintoticamente è O(m), e poichè avviene in un do-while potenzialmente infinito, la complessità
	di tutta la funzione menu è MAX*O(m) dove MAX è l'ipotetico limite massimo di volte in cui non si sceglie il numero 7 che fa finire tutto.
	spazio:
	Nel menù si usa la struttura di una lista di n pc che ha a sua volta delle liste di m jobs, occupando uno spazio asintotico O(n+m).
}