Abbassare complessità di un algoritmo

di il
3 risposte

Abbassare complessità di un algoritmo

Gentili utenti,
ho risolto un esercizio con complessità O(n^2) ma devo farla scendere a O(n) o al max O(nlogn) ma non riesco poiché lavoro con due vettori e quindi due cicli for. Allora ho pensato a un escamotage matematico che però non funziona sempre.
Avrei bisogno di aiuto ma non posso postare il mio pseudocodice poiché potrebbero reperirlo altre persone.
C'è qualcosa che mi sfugge ma non capisco cosa e sto impazzendo.
come posso fare per chiedere aiuto?

3 Risposte

  • Re: Abbassare complessità di un algoritmo

    VentoNelGrano ha scritto:


    come posso fare per chiedere aiuto?
    Spiega almeno di che cosa si sta parlando, del contesto, di cosa fa l'algoritmo. Altrimenti nessuno credo potrà aiutarti ....
  • Re: Abbassare complessità di un algoritmo

    andbin ha scritto:


    VentoNelGrano ha scritto:


    come posso fare per chiedere aiuto?
    Spiega almeno di che cosa si sta parlando, del contesto, di cosa fa l'algoritmo. Altrimenti nessuno credo potrà aiutarti ....
    L'esercizio dice che dati in input due vettori di uguale dimensione, questi rappresentano i vincoli del gioco. Ad esempio: (211) mi dice che sulla prima riga di una griglia posso marcare al massimo due caselle, sulla seconda riga 1 e cosi via.
    Stesso discorso per le colonne: se ho (201) sulla prima colonna ne posso marcare due, sulla seconda 0 e così via.
    Il problema è trovare il massimo delle caselle che posso marcare.
    So risolvere il problema, ho uno pseudocodice e un ragionamento, ma troppo costoso e vorrei parlarne con qualcuno che mi aiuti a far scendere la complessità senza però postarlo qui o far leggere le risposte pubblicamente.
  • Re: Abbassare complessità di un algoritmo

    VentoNelGrano ha scritto:


    Ad esempio: (211) mi dice che sulla prima riga di una griglia posso marcare al massimo due caselle, sulla seconda riga 1 e cosi via.
    Stesso discorso per le colonne: se ho (201) sulla prima colonna ne posso marcare due, sulla seconda 0 e così via.
    Il problema è trovare il massimo delle caselle che posso marcare.
    A me ... continua a non essere chiaro: quindi 211 e 201 intendi due array? di int? E quale è la connessione tra questi due? La somma dei due valori ad una certa riga e colonna?

    VentoNelGrano ha scritto:


    So risolvere il problema, ho uno pseudocodice e un ragionamento, ma troppo costoso
    Se come intendevi hai un doppio ciclo, quindi N x N, allora sì la complessità è O(n²) .
    Ma se all'atto pratico è davvero pesante o no dipende anche dal numero di elementi. Se mi parli di N = 100000 allora sì qualche problemino di performance c'è. Se mi parli di 3, 10, 100 no.
Devi accedere o registrarti per scrivere nel forum
3 risposte