PDF de programación - Ejercicios resueltos programación III

EJERCICIOS RESUELTOS 
PROGRAMACIÓN III 
      

 

Curso 2008 ‐ 2009 

 

 

 

 

 

 

 

 

 

 

 



Ejercicios resueltos de programación 3



Tema 3. Notación asintótica.

Alumna: Alicia Sánchez
Centro: UNED-Las Rozas (Madrid)



El índice de los ejercicios será el siguiente. Se observa que sólo hay cuestiones de exámenes
(de los ejercicios cortos), por lo que se debería hacer hincapié en ellos:

1.
Introducción teórica ………………………………………………………………………………. 3
2. Cuestiones de exámenes ………………………………………………………………………. 6



Ejercicios tema 3


Curso 2007/08

Página 2 de 9


Introducción teórica:
Previo a resolver los ejercicios pondremos un poco de teoría, que nos vendrá bien para luego
hacer los ejercicios:

Empezaremos viendo las distintas notaciones, para “el orden de”, cota inferior y orden exacto:

- Notación para el orden de (cota superior):



Gráficamente sería:



Es conveniente disponer de un símbolo matemático para representar el orden de.

Sea :ℕ→ℝ una función arbitraria de los números naturales en los reales no
negativos. Le indicará mediante () el conjunto de todas las funciones
:ℕ→ℝ tales que ()≤∗(), para todo ≥ para una constante
positiva c y un umbral entero . En otras palabras:
()≡{:ℕ→ℝ|∃ ∈ ℝ,∈ℕ,∀ ≥|()≤∗()}
()

()

(umbral)
siendo: : Cierto umbral del tamaño del problema.
(): Acota superiormente a la función ().
Matemáticamente, esto significa que existe una constante real positiva y un
umbral entero tal que ()≥∗() siempre que ≥.
()≡{:ℕ→ℝ|∃ ∈ ℝ,∈ℕ,∀ ≥|()≥ ∗()}
() ∈(): Cota inferior.

()∈(): Cota superior.

Gráficamente sería:



- Notación para la cota inferior:



()≈
()



(umbral)



Ejercicios tema 3


Curso 2007/08

Página 3 de 9





- Notación para el orden exacto:

Diremos que () está en Theta de (), o lo que es igual que () está en el
orden exacto de () y lo denotamos ()∈(), si () pertenece tanto a
() como a Ω().
La definición formal de es:
()=()∩Ω().
Por tanto, ()≡{:ℕ→ℝ|∃ , ∈ ℝ,∈ℕ,∀ ≥|
∗()≤()≤ ∗()}.
superiormente por (). Podemos probarlo tanto por la definición como por la
Para demostrar que una función dada no pertenece al orden de otra función ()
positiva tal que ()≤∗() para todos los ≥1 (tomaremos como 1,

- Demostración por contradicción: Es la forma más sencilla. Consiste en
demostrar la veracidad de una sentencia demostrando que si negación da lugar a
una contradicción.

- La regla del umbral generalizado: Implica la existencia de una constante real y

regla del límite.


tendremos estas formas:

nos interesa más la definición dada por la regla del umbral sin generalizar).



Decimos que el conjunto del orden exacto está acotado tanto inferior como



- La regla del límite: Lo definiremos completamente tras analizar la cota superior

y el coste exacto.



La primera y segunda manera no la usaremos por norma general, ya que no nos compensará.
En cuanto a la última será la que usemos, de nuevo recordaremos la definición y lo que
significa cada resultado:



Ejercicios tema 3


Curso 2007/08

Página 4 de 9

La regla del límite: Nos permite comparar dos funciones en cuanto a la
notación asintótica se refiere. Tendremos que calcular el siguiente límite:

Se nos darán 3 resultados:

Estas funciones se comportan igual. Se diferencian en una constante
multiplicativa.


lim→()().
1. lim→()()=∈ ⇒
⇒ ()∈() ()∈() ()∈()
()∈() ()∈() ()∈().
2. lim→()()=∞ ⇒
⇒ ()∉() ()∈() ()∉()
()∈() ()∉() ()∉().
Por muy alta que sea la constante multiplicativa de () nunca superará a
().
3. lim→()()=0 ⇒
⇒ ()∈() ()∉() ()∉()
()∉() ()∈() ()∉().
() crece más exponencialmente que (). Sería su cota superior.



Ejercicios tema 3


Curso 2007/08

Página 5 de 9


1ª parte. Cuestiones de exámenes:
Febrero 2002 -2ª (ejercicio 2)

Enunciado: Un algoritmo de coste ( ) tarda 15 segundos en realizar un determinado

procesamiento sobre un ordenador a 450 MHz. ¿Cuánto tiempo se tarda en realizar el mismo
procesamiento con el mismo algoritmo en una máquina 3 veces más lenta?

Respuesta: Se nos plantea un problema en el que cambia la velocidad, que equivale a la
implementación. En este caso, se divide por tres la velocidad, lo que implica que tarda aún
más. Serían 15 seg. * 3 = 45 seg.
Si en esta misma máquina cambiamos el tamaño del problema al doble tardaremos 4 veces

más ((2∗)=4∗), si es triple serian 9 veces más, siguiendo el planteamiento anterior.
de ()”? Demostrar que ()=5∗2+ está en el orden exacto de 2.

Enunciado: ¿Qué significa que el tiempo de ejecución de un algoritmo está “en el orden exacto

Diciembre 2003 (ejercicio 1)



Respuesta:



Al resolverla llegamos a una indeterminación, por lo que aplicaremos el teorema de L'Hôpital
tantas veces como sea necesario hasta llegar a una conclusión coincidiendo con cualquiera de
los casos anteriores:

Para la primera pregunta tendremos que poner la definición previamente escrita en la teoría o
bien en el resumen del tema. No la pondremos, por estar en este mismo documento, en
páginas anteriores.
Para la segunda pregunta emplearemos la regla del límite. En este caso, tomaremos

()=5∗2+ y ()=2. Pasamos a resolver el límite, como sigue:
lim→∗

=lim→∗∗(cid:304