Complessità delle chiamate ricorsive

1

il mio cervello è un po 'bloccato mentre sto cercando di compilare un esempio per il mio blog. Sto presentando un algoritmo che disegna un numero da un array, lo aggiunge a una somma e si chiama in modo ricorsivo.

func solve(coins: Array<Int>, target: Int) -> Int {

    func _solve(coins: Array<Int>, current: Int) -> Int {

        var candidates = coins
        var crt = current
        while candidates.count > 0 {
            // pop() removes the element at the head and returns it
            let rdm: Int = candidates.pop() 

            if (current + rdm) > target {
                continue
            }

            crt = _solve(candidates, current: current + rdm)

            if crt == target {
                return crt
            }

        }
        return crt
    }

    return _solve(coins, current: 0)
}

Ciò che questo algoritmo sta facendo è, dato un insieme di monete, cercare di avvicinare un dato bersaglio il più vicino possibile.

Qual è la complessità di questo algoritmo?

    
posta Mike M 05.04.2016 - 10:51
fonte

1 risposta

4

Non importa che tu scelga la moneta successiva casualmente piuttosto che sistematicamente. Stai ancora potenzialmente provando tutti i sottoinsiemi di un multiset di dimensione N, quindi potrebbero essere necessari fino a 2 ^ N tentativi, e questa è la tua (massima) complessità.

    
risposta data 05.04.2016 - 10:59
fonte

Leggi altre domande sui tag