Quiz Complessità

Regole per le crocette:
1) Omega è un limite inferiore.
    es. Omega(n^5) fai una riga a n^5 e cancelli lo spazio sotto.
2) O è un limite superiore.
    es. O(n^2) fai una riga a n^2 e cancello lo spazio sopra.
3) Theta è un limite superiore e inferiore
    es. Theta(n^3) fai una riga a n^3 e cancelli tutto lo spazio sopra e tutto lo spazio sotto.
    (Rimane una riga bianca su n^3).
4) O non conta come limite superiore per i PROBLEMI, ma solo per gli algoritmi.
    es. Ho un problema O(n^2) quindi dovrei fare una riga a n^2 e cancellare lo spazio sopra
    poiché O è un limite superiore. Invece NO. Perché "Avere un problema O(n^2)" vuol dire
    "Avevo un problema, e il migliore algoritmo che ho trovato è O(n^2)".

    Conclusione se ho un problema O(qualcosa) possono risolverlo sia algoritmi peggiori
    trovati da programmatori più scarsi di me, che algoritmi migliori trovati da Dijkstra xD.

Rileggi.


- Un problema Omega( n4 ) può essere risolto da un algoritmo Omega( n2 ).
  Un algoritmo Omega(n^2): faccio una riga su n^2 e tolgo tutto lo spazio sotto, quindi ogni
  cosa sopra va bene. Per soddisfare la condizione Omega(n^4) devo considerare lo spazio sopra n^4.
  Facendo l'intersezione tra gli spazi che sono rimasti, esce che qualsiasi cosa sopra n^4 soddisfa
  la condizione. Quindi Vera.

- Un problema Omega( n4 ) può essere risolto da un algoritmo Omega(n5).
  Levo tutto lo spazio sotto n^4, Levo tutto lo spazio sotto n^5, faccio l'intersezione.
  Rimane tutto lo spazio sopra n^5. Vera.

- Ho trovato un algoritmo O( n2 ) per un problema O( n3 )
  Ho un problema O(n^3) vuol dire "Ho trovato un algoritmo O(n^3) per il mio problema".
  Quindi potrei benissimo trovarne anche uno migliore, O(n^2). Vera.

- Ho trovato un algoritmo O( n7 ) per un problema O( n2 )
  Vera. Non c'è limite al peggio.

- Ho trovato un algoritmo Theta( n3 ) per un problema Theta( n4 )
  Un problema Theta(n^4) diventa O(n^4) e Omega(n^4):
    * Omega(n^4) -> faccio una riga su n^4 e cancello tutto lo spazio sotto.
    * O(n^4) -> vuol dire che ho trovato un algoritmo O(n^4) per il mio problema.
  Ora analizziamo l'algoritmo Theta(n^3):
    * Omega(n^3) -> faccio una riga su n^3 e cancello tutto lo spazio sotto.
    * O(n^3) -> faccio una riga su n^3 e cancello tutto lo spazio sopra.
  Facendo l'intersezione non rimane spazio libero. Quindi è falsa.

- Ho trovato un algoritmo Omega(n) per un problema Theta(n4)
  La parte del problema è uguale a prima.
  Ora faccio una riga su n e cancello lo spazio sotto.
  Tutto lo spazio sopra n^4 è libero. Vera.

- Ho trovato un algoritmo Omega(n7) per un problema Theta(n4)
  La parte del problema è uguale a prima.
  Tutto lo spazio sopra n^7 è libero. Vera.


Ora queste regole funzionano con le domande che ho provato fin'ora ...
per il resto non garantisco nulla :P