Che cosa significa quando diciamo che alcune funzioni sono polinomialmente più grandi / più piccole di qualche altra funzione?

Question

Che cosa significa quando diciamo che alcune funzioni sono polinomialmente più grandi / più piccole di qualche altra funzione?

#1 da (8 voti)

3

Stavo esaminando questo video lezione sul teorema master da Introduzione all'algoritmo e mentre si spiega il caso A del maestro teorema professore dice che alcune funzioni f(n) sono polinomialmente più piccole di qualche altra funzione al punto 53:08 secondi:

Che cosa significa per una funzione essere polinomialmente più piccola di questa funzione?

Sono confuso qui come polinomiale non è equivalente a poly-logaritmicamente. Il professore ha usato il termine sbagliato qui? È altamente improbabile anche se continua a dire lo stesso termine un numero di volte.

algorithms complexity

posta Geek 30.07.2012 - 17:31

fonte

1 risposta

Leggi altre domande sui tag algorithms complexity

Disegnare un documento con strategie per far fronte ai "disastri" Test funzionali nella verifica

score 8 · Accepted Answer

In breve: un esponente più piccolo (più grande) di n.

Si riferisce direttamente a una parte della mia risposta a una tua precedente domanda qui :

,cheinpraticadicechenperunpo'dienergiacrescepiùvelocemente,sel'esponenteèpiùgrande,indipendentementedafattoricostanti.

Nelcaso1,sipresumechelafunzionef(n)siapolinomialmentepiùpiccoladiquesta:

Non essere spaventato dal logaritmo qui, è solo un numero , perché a e b sono costanti, quindi è log_b(a) . (Questo è il motivo per cui poly-logaritmicamente non entra nell'immagine, in quel caso)

Viene quindi definito a quale classe di funzioni f(n) deve appartenere. Questa è già la risposta alla tua domanda "what it means to be polynomially smaller" :

Tuttociòsignificachel'esponentedindeveessereinferiorealog_b(a):devisottrarreunnumeropositivo(epsilon)daesso.

Questoèunaltromododiguardarlo:

Il polinomialmente più grande ha più fattori di n: epsilon di più. (o meno nel caso di più piccoli)

A 57:30 fornisce un esempio, dove finisce nel caso 1: confronta f(n) = n con n^2 . f(n) è polinomialmente più piccolo perché 1 < 2 .