recursividad

                        
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), porlo 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 distintasnotaciones, para “el orden de”, cota inferior y orden exacto:

-

Notación para el orden de (cota superior):
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
( ) el conjunto de todas las funciones
negativos. Le indicará mediante
: ℕ → ℝ tales que ( ) ≤ ∗ ( ), para todo ≥
para una constantepositiva c y un umbral entero . En otras palabras:
( ) ≡ { : ℕ → ℝ |∃

∈ ℝ ,

∈ ℕ, ∀

≥

| ( ) ≤ ∗ ( )}

Gráficamente sería:
( )
( )
(umbral)
siendo:
: Cierto umbral del tamaño del problema.
( ): Acota superiormente a la función ( ).
-

Notación para la cota inferior:
Matemáticamente, esto significa que existe una constante real positiva
umbral entero
tal que ( ) ≥ ∗ ( )siempre que ≥ .
( ) ≡ { : ℕ → ℝ |∃

∈ ℝ ,

∈ ℕ, ∀

≥

| ( )≥

y un

∗ ( )}

Gráficamente sería:
( )≈

( ) ∈

( ) : Cota inferior.

( )∈

( ) : Cota superior.

( )
(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
( ) , si ( ) pertenece tanto aorden exacto de ( ) y lo denotamos ( ) ∈
( ) como a Ω ( ) .
La definición formal de
( ) =

es:

( ) ∩Ω

( ) .

Por tanto,
( ) ≡ { : ℕ → ℝ |∃ ,

∈ ℝ ,

∈ ℕ, ∀

∗ ( )≤ ( )≤

≥

|

∗ ( )}.

Decimos que el conjunto del orden exacto está acotado tanto inferior como
superiormente por ( ). Podemos probarlo tanto por la definición como por la
regla del límite.
Para demostrarque una función dada no pertenece al orden de otra función
tendremos estas formas:

( )

-

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
positiva tal que ( ) ≤ ∗ ( ) para todoslos ≥ 1 (tomaremos
como 1,
nos interesa más la definición dada por la regla del umbral sin generalizar).

-

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 quesignifica 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:
lim

( )
→

( )

.

Se nos darán 3 resultados:
1. lim
⇒

( )
→

( )

=

∈

⇒

( )∈

( )

( )∈

( )

( )∈

( )

( )∈

( )

( )∈

()

( )∈

( )

.

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

2. lim
⇒

( )
→

( )

=∞⇒

( )∉

( )

( )∈

( )

( )∉

( )

( )∈

( )

( )∉

( )

( )∉

( )

Por muy alta que sea la constante multiplicativa de
( ).

3. lim
⇒

( )
→

( )∈
( )∉

( )

.

( ) nunca superará a

=0⇒
( )
( )

( )∉
(...