Diferencia entre revisiones de «Teorema del aumento de velocidad»
mSin resumen de edición |
m Bot: unificando... |
||
| Línea 9: | Línea 9: | ||
The '''[[quadratic speedup theorem]]''' for [[quantum computer]]s proves that if a deterministic computer can carry out a search in time O(f(''n'')) then a quantum computer can carry out the same search in time O(√f(''n'')). |
The '''[[quadratic speedup theorem]]''' for [[quantum computer]]s proves that if a deterministic computer can carry out a search in time O(f(''n'')) then a quantum computer can carry out the same search in time O(√f(''n'')). |
||
[[ |
[[Categoría:Teoremas]] |
||
[[ |
[[Categoría:Clases de complejidad]] |
||
[[de:Speedup-Theorem]] |
[[de:Speedup-Theorem]] |
||
Revisión del 18:21 10 mar 2006
En la teoría de la complejidad computacional, el teorema del aumento de velocidad considera un algoritmo que resuelva un problema y demuestra que existe otro más rapido, que resuelve el mismo problema (o utilizando una menor cantidad de cualquier recurso, no solo tiempo).
El teorema del aumento de velocidad linear para máquinas de Turing prueba que dado cualquer máquina que resuelva un problema usando f(n) de un recurso, existe otra maquina que lo resueve utilizando cf(n) de ese mismo recurso, donde c > 0.
Blum's speedup theorem demonstrates the existence of a problem such that if any algorithm can solve it in time O(f(n)), there is another algorithm that solves it in time O(log f(n)).
The quadratic speedup theorem for quantum computers proves that if a deterministic computer can carry out a search in time O(f(n)) then a quantum computer can carry out the same search in time O(√f(n)).