Deje [math] k \ in \ mathbb {R} [/ math] y [math] j \ in \ mathbb {R} ^ + [/ math]. Suponga que las funciones [math] f: \ mathbb {N} \ to \ mathbb {R}, g: \ mathbb {N} \ to \ mathbb {R} [/ math] se definen como [math] f (n): = (n + k) ^ j [/ matemáticas], [matemáticas] g (n): = n ^ j [/ matemáticas]. ¿Cómo mostramos que [matemáticas] f = \ Theta (g) [/ matemáticas]?
Necesitamos mostrar la existencia de [math] c_1, c_2 \ in \ mathbb {R} ^ + [/ math], [math] n_0 \ in \ mathbb {N} [/ math] tal que [math] 0 \ le c_1g (n) \ le f (n) \ le c_2g (n) [/ math] para todos [math] n \ ge n_0 [/ math].
Si [matemáticas] k = 0 [/ matemáticas], entonces esto es trivial. Elija [math] c_1 = c_2 = n_0 = 1 [/ math], y ya está.
- Cómo resolver la siguiente ecuación recursiva
- ¿Es teóricamente posible que un algoritmo tenga una complejidad negativa?
- ¿Qué importancia tiene UPTU para la universidad de informática de MNN en Allahabad?
- Cómo dejar de hacer preguntas mientras aprende ingeniería
- ¿Qué es un algoritmo para convertir de una lista de adyacencia a una matriz de incidencia?
Suponga que [matemáticas] k> 0 [/ matemáticas]. Tenemos [matemáticas] n ^ j <(n + k) ^ j [/ matemáticas].
También tenemos [matemáticas] (1 + k) ^ j \ ge \ left (1+ \ dfrac {k} {n} \ right) ^ j = \ dfrac {(n + k) ^ j} {n ^ j} [/ math] para todos [math] n \ in \ mathbb {N} [/ math].
Por lo tanto, [math] (n + k) ^ j \ le (1 + k) ^ jn ^ j [/ math] para todos [math] n \ in \ mathbb {N} [/ math].
Elija [matemáticas] c_1: = 1, c_2: = (1 + k) ^ j, n_0: = 1 [/ matemáticas]. Luego tenemos [math] 0 \ le c_1 n ^ j \ le (n + k) ^ j \ le c_2 n ^ j [/ math] para todos [math] n \ ge n_0 [/ math]. Por lo tanto [matemáticas] (n + k) ^ j = \ Theta (n ^ j) [/ matemáticas].
Suponga que [matemática] k <0 [/ matemática]. Como [matemática] k 0 [/ matemática] tal que [matemática] k = -m [/ matemática]. Por lo tanto, tenemos [matemáticas] (n + k) ^ j = (nm) ^ j [/ matemáticas].
Tenemos [math] (nm) ^ j <n ^ j [/ math] para todos [math] n \ in \ mathbb {N} [/ math].
Tenga en cuenta que para [matemáticas] n> m + 1 [/ matemáticas] tenemos [matemáticas] 0 <1- \ dfrac {m} {m + 1} <1- \ dfrac {m} {n} [/ matemáticas].
Por lo tanto, [matemáticas] \ left (1- \ dfrac {m} {m + 1} \ right) ^ j m + 1 [/ math].
Por lo tanto, [matemática] \ left (1- \ dfrac {m} {m + 1} \ right) ^ jn ^ j m + 1 [/ math] .
En otras palabras, tenemos
[matemática] \ left (\ dfrac {1} {1-k} \ right) ^ jn ^ j 1-k [/ math].
Elija [matemáticas] c_1: = \ left (\ dfrac {1} {1-k} \ right) ^ j, c_2: = 1, n_0: = \ left \ lceil {1-k} \ right \ rceil [/ math ]
Entonces tenemos [math] 0 \ le c_1n ^ j \ le (n + k) ^ j \ le c_2n ^ j [/ math] para todos [math] n \ ge n_0 [/ math]. Así [matemáticas] (n + k) ^ j = \ Theta (n ^ j) [/ matemáticas]
En todos los casos, [matemática] k = 0, k> 0, k <0 [/ matemática], tenemos [matemática] (n + k) ^ j = \ Theta (n ^ j) [/ matemática].
