Come possiamo dimostrare che il tempo di esecuzione di un algoritmo è limitato?

Question

Supponiamo di poter dimostrare che un algoritmo, invocato con un input di dimensioni n, viene eseguito nel tempo O(f(n)).

Voglio dimostrare che questo tempo di esecuzione è limitato. Due domande:

1. Non sarebbe sufficiente fornire un input speciale e mostrare che il tempo di esecuzione è almeno f(n)?
2. Ho letto che una possibilità per dimostrare la tenuta è "ridurre l'ordinamento ad esso". Non ho idea di che cosa si intende con questo

Answer 1

Non sarebbe sufficiente a dare un ingresso speciale e mostrare che la corsa tempo è di almeno f (n)?

Sì, supponendo che stanno parlando del caso peggiore complessità.
Se si parla della peggiore complessità del caso - e si è dimostrato che è in esecuzione nel O(f(n)), se si trova un input "peggiore" di C*f(n)) per alcuni costanti C - si è effettivamente dimostrato che l'algoritmo (nel peggiore delle prestazioni) è in Ω(f(n)) e dal O(f(n)) [intersection] Ω(f(n)) = Theta(f(n)), significa che l'algoritmo è in esecuzione nel Theta(f(n)) nella peggiore analisi del caso.
Nota che dovrebbe in realtà essere una "famiglia" di esempi, dal momento che se io sostengo "Sì, ma questo è corretto solo per piccoli n valori, e non per n>N (per alcuni N), mi si può dimostrare che questo famiglia di esempi copre anche il caso in cui n>N, ed essere ancora valida.

Simmetricamente, se hai dimostrato un algoritmo ha migliori prestazioni caso di Ω(f(n)), e hai trovato qualche input che corre "migliore" (più veloce) rispetto C*f(n)) per un po ' costante C, avete effettivamente dimostrato che l'algoritmo è Theta(f(n)) nella migliore analisi del caso

Questo trucco NON funziona per l'analisi del caso medio, in cui è necessario calcolare l'attesa del tempo di esecuzione e un esempio singolare non è utile.

Ho letto che una possibilità per dimostrare la tenuta è "ridurre lo ordinamento ". Non ho idea di che cosa si intende con questo

Questo viene fatto per dimostrare una pretesa molto più forte, che non v'è alcun algoritmo (a tutti) che può risolvere qualche problema al momento desiderato.
L'utilizzo comune è di presupporre l'algoritmo della scatola nera A che viene eseguito in alcuni periodi o(g(n)) e quindi utilizzare A per creare un algoritmo di ordinamento che viene eseguito nel tempo o(nlogn). Tuttavia, poiché l'ordinamento è il problema Ω(nlogn), abbiamo una contraddizione e possiamo concludere che le ipotesi su A sono errate e che non possono essere eseguite nel momento desiderato.

Questo ci aiuta a dimostrare un reclamo più forte: non solo il nostro algoritmo ha questo limite inferiore, ma TUTTI gli algoritmi che risolvono il problema specifico hanno questo limite inferiore.

Answer 2

annuncio 1: Sì, ma è necessario essere in grado di trovare tale input di dimensione n per qualsiasi n. Un esempio di dimensione 3 che viene elaborato in 9 passaggi non dimostra nulla.

annuncio 2: se è possibile modificare una sequenza di elementi in modo che il proprio algoritmo la smista in modo efficace (si ottiene una sequenza ordinata dopo l'elaborazione dell'output), si è ridotto l'ordinamento ad esso. E poiché l'ordinamento (per confronto) non può essere più rapido di O (n log (n)), questo può essere usato per dimostrare che il tuo algoritmo non può essere più veloce di O (n log (n)).

Ovviamente, le funzioni di elaborazione di input e output non possono essere più lente o uguali a O (n log (n)) perché questo argomento sia valido, altrimenti è possibile ordinare l'array e provare che un algoritmo O (1) che restituisce appena l'array di input è in realtà almeno O (n log (n)) :).