Big O di 2 interessanti funzioni algoritmiche [chiuso]

0

Questo è il mio compito (l'ho provato e non ci sono riferimenti per domande come queste)

Determina se queste funzioni sono o meno tempo di esecuzione polinomiale e determina la costante c per O (n ^ c) in base a queste funzioni:

3^(log base2 (n))

(log base2 (n))!

La mia intuizione mi dice di sì per entrambi.

Caso 1: l'esponenziale sarà sempre dominante, indipendentemente dal numero inserito come n. dal suo log base 2, crescerà "esponenzialmente" man mano che n è aumentato .. tuttavia non so come dimostrarlo

Caso 2: uso di n! come riferimento, poiché n! è equivalente 2 ^ n, quindi (log base2 (n))! deve essere equivalente a 2 ^ (log base 2 (n))

    
posta Apprentice Programmer 06.01.2015 - 07:12
fonte

2 risposte

3
  1. Calcola log (3 ^ (log_2 (n)))

  2. n! non è equivalente a 2 ^ n. Vedi l'approssimazione di Stirling per il fattoriale.

risposta data 06.01.2015 - 07:35
fonte
1

Dato che questo è chiaramente compito a casa, non ho intenzione di buttare le risposte là fuori, ma ti darò alcuni suggerimenti per affrontarle.

Per il tuo primo problema, devi ripensare alla definizione di un logaritmo. Quale sarebbe la risposta se fosse questo?

2^(log base2 (n))

Se inserisco quattro in per n, il log valuterà a due. Il potere dovrebbe quindi valutare a quattro. Se inserisco 8 in, ottengo 8. In altre parole, qualsiasi base b elevata alla base di log b di qualsiasi valore n restituisce < em> n . L'esponenziazione e il log si annullano a vicenda con la stessa base .

Cosa succede se l'esponenziazione ha una base più ampia del logaritmo? Base più piccola? Quanto velocemente crescono i polinomi rispetto a quelli in elevazione e registri indipendentemente dalla base?

Per il secondo problema, cosa succede quando applichi un esponenziale o fattoriale a una funzione che è polinomiale o inferiore? Ciò che domina a lungo termine, assumendo che tu non stia facendo 2 ^ (log 2 (n)) o qualcos'altro che annulla?

Ricorda che con Big-Oh devi pensare a tendenze arbitrariamente grandi. Numeri non specifici, basti pensare che se guardassi in basso all'asse n trilioni di valori, qual è il fattore dominante? Potrei tracciare 1.00000000000000000000000001 n e rimarrà molto piccolo per un tempo lungo ma alla fine crescerà più velocemente di n 10000000000000000 . Concesso in pratica il primo è preferibile al secondo, ma qui stiamo parlando di teoria, non di algoritmi di qualità di produzione.

    
risposta data 06.01.2015 - 07:42
fonte

Leggi altre domande sui tag