Come può un algoritmo avere due peggiori complessità? Capitolo 1 esercizio

Question

di Steven Skiena manuale di progettazione L'algoritmo ha questa domanda:

Sia P un problema. La complessità temporale del caso peggiore di P è O (n^2). Anche la complessità del tempo peggiore di P è Ω (n log n). Sia A un algoritmo che risolva P. Quale sottoinsieme delle seguenti affermazioni è coerente con questa informazione sulla complessità di P?

• A ha la complessità del tempo nel caso peggiore O (n^2).
• A ha la complessità del tempo nel caso peggiore O (n^3/2).
• A ha la complessità del tempo nel caso peggiore O (n).
• A ha una complessità temporale peggiore ⍬ (n^2).
• A ha una complessità temporale peggiore ⍬ (n^3).

Come può un algoritmo avere due complessità temporali nel caso peggiore? L'autore sta cercando di dire che per un valore di n (ad esempio 300) il limite superiore dell'algoritmo scritto per risolvere P è dell'ordine di O (n^2) mentre per un altro valore di n (ad esempio 3000) il lo stesso algoritmo era Ω (n log n)?

Answer 1

La risposta alla tua domanda specifica

è l'autore cercando di dire che per un certo valore di n (diciamo per esempio 300) limite superiore per l'algoritmo scritto per risolvere P è dell'ordine di O (n^2) mentre per un altro valore di n (diciamo ad esempio 3000) lo stesso algoritmo nel caso peggiore era Ω (n log n)?

è no. Non è così che funzionano le funzioni di complessità. :) Non parliamo di classi di complessità diverse per diversi valori di n. La complessità si riferisce all'intero algoritmo, non all'algoritmo a dimensioni specifiche. Un algoritmo ha una funzione di complessità unica T (n), che calcola quanti passaggi sono necessari per eseguire il calcolo per una dimensione di input di n.

Nel problema, si sono date due informazioni:

• Il caso peggiore complessità è O (n^2)

• Il caso peggiore complessità è Ω (n log n)

Tutto questo significa che siamo in grado di raccogliere le costanti c1, c2, N1, N2 e, in modo tale che, per la funzione del nostro algoritmo T (n), abbiamo

0.123.

• T (n) ≤ c1 * n^2 per ogni n ≥ N1

• T (n) log ≥ c2 * n n per ogni n ≥ N2

In altre parole, la nostra T (n) è "asintoticamente delimitata sotto" da un certo tempo costante n log n e "asintoticamente limitato sopra" da alcune volte costanti n^2. Può essere esso stesso qualsiasi cosa "tra" una funzione di stile n log n e una funzione stile n^2. Può anche essere n log n (poiché è limitato sopra da n^2) o può essere n^2 (poiché è limitato di seguito da n log n. Può essere qualcosa nel mezzo, come n (log n) (log n).

Non è tanto che un algoritmo ha "molteplici complicanze nel caso peggiore" nel senso che ha comportamenti diversi. "Quello che vedi è un limite superiore e un limite inferiore!" E questi possono, ovviamente, essere . diversa

Ora è possibile di avere una qualche funzione "strano" come questo:

def p(n): 
    if n is even: 
     print n log n stars 
    else: 
     print n*2 stars 

questo algoritmo pazzo fa h come i limiti specificati nel problema dal libro di Skiena. E non ha la complessità Θ. Potrebbe essere stato quello a cui stavi pensando, ma tieni presente che non è necessario che una funzione di complessità sia così strana per poter dire che i limiti superiore e inferiore differiscono. La cosa da ricordare è che i limiti superiore e inferiore non sono stretto se non espressamente dichiarato di essere così.