Respuestas
¿Demasiados anuncios?
Steven esencialmente ha dado la respuesta (con un error menor). Aquí es cómo se puede llegar a él. Voy a hacer la mitad de la derivación; la otra mitad es el mismo, pero te intercambio de la mayoría de las $\le$ $\ge$ y reemplazar todos los grandes-O grandes-$\Omega$.
Usted sabe que $T(n) = T(n-1)+\Theta(n)$, así que usted sabe que $T(n) = T(n-1)+O(n)$, por lo que hay un $c>0$ tal que $$T(n)\le T(n-1)+cn $$ para todos los $n$ lo suficientemente grande. Somos sido entregado a nuestra conjetura, es decir, que $T(n)=O(n^2)$ así que yo creo que va a ser que $T(n)\le kn^2$ algunos $k>0$ y todos los $n$ lo suficientemente grande. En la fase de descubrimiento, vamos a intentar buscar una $k$ en términos de la $c$ tenemos.
Para nuestra $k$ hemos $$ \begin{align} T(n)&\le T(n-1)+cn\\ &\le k(n-1)^2+cn \end{align} $$ y necesitamos que $T(n)\le k(n-1)^2+cn\le kn^2$. Tenemos esta cadena de resultados $$ \begin{align} k(n-1)^2+cn&\le kn^2\\ k(n^2-2n+1)+cn&\le kn^2\\ kn^2-2kn+k+cn&\le kn^2\\ -2kn+k+cn&\le 0\\ k(1-2n)&\le-cn\\ k(2n-1)&\ge cn\\ k&\ge \frac{cn}{2n-1} \end{align} $$ así, desde el mayor valor de $n/(2n-1)$ $n\ge 1$ $1$ cualquier $k\ge c$ va a trabajar. Vamos a ver de que esta hecho el trabajo con $k=c$. $$ \begin{align} T(n)&\le T(n-1) +cn &\text{given}\\ &\le c(n-1)^2+cn &\text{by assumption}\\ &=cn^2-2cn+c+cn\\ &=cn^2-cn+c\\ &=c(n^2-n+1)\le cn^2 &\text{ta daa!} \end{align} $$ mientras $n\ge 1$, por lo que, de hecho,$T(n)=O(n^2)$. Como dije, la otra dirección es inmediata.
En mi humilde opinión, una mejor manera de expresar la pregunta sería: "si $g(n)\in\Theta(n)$ $T(n)$ está definido por $T(n) = T(n-1)+g(n)$, muestran que $T(n)\in\Theta(n^2)$"; esto subraya el papel de la $\Theta(n)$ como una clase de funciones, no una individual.
Un lugar para comenzar sería reescribir su definición recursiva de $T(n)$ en una mucho más explícita: si expande un par de pasos de la recursividad, un patrón debe quedar claro ( $T(n) = T(n-1)+g(n) = T(n-2)+g(n-1)+g(n)=\ldots$ ); ¿puede usted imaginar cómo utilizar esta opción para escribir una definición de $T(n)$ que no implica la recursividad?
Una vez que usted tiene la expresión de la expansión de la definición recursiva de $T()$, usted puede empezar a enchufar la maquinaria alrededor de la $\Theta()$ nota: la definición de la clase $\Theta(n)$ es que el $g(n)\in\Theta(n)$ si hay constantes $g_1$ $g_2$ tal que para todo $n$, $g_1\cdot n\leq g(n)\leq g_2\cdot n$. Los límites inferior y superior en los valores individuales de $g()$ debe dejar que le vinculan con la expresión que se encuentra en el primer paso, puede que desee tener en cuenta la fórmula que $\sum_{i=0}^n i = \frac{n(n+1)}{2}$.
Finalmente, una vez que tienes un nuevo conjunto de límites para su función de $T()$ usted puede ir a otro lado, y tratar de encontrar nuevas constantes $T_1$ $T_2$ tal que $T_1\cdot n^2\leq T(n)\leq T_2\cdot n^2$ todos los $n$. (Tenga en cuenta que $T_1$ $T_2$ deberán ser expresadas en términos de las constantes de la $g_1$ $g_2$ que usted está garantizado para $g()$.) Una vez que tenga estos te han demostrado su afirmación de que $T(n)\in\Theta(n^2)$.
Para hacer el problema con el método de sustitución, un enfoque similar puede ser tomado; aquí se comenzaría por la cosecha 'constantes' $T_1$ $T_2$ (a se especifica más adelante) para la definición de $T(n)\in\Theta(n^2)$, así como asumir las constantes $g_1$ $g_2$ especificado por el problema de la condición de que $g(n)\in\Theta(n)$. Se puede decir entonces que $$\begin{align} T(n) &= T(n-1)+g(n) \\ &\leq T(n-1) + g_2\cdot n && \text{by the definition of %#%#%} \\ &\leq T_2\cdot (n-1)^2+g_2\cdot n&& \text{by the definition of %#%#%} \\ &=T_2 n^2+(g_2-2T_2)n+T_2&& \text{by algebra} \\ \end{align}$$ Y, entonces usted necesita para encontrar una manera de elegir un $g(n)\in\Theta(n)$ tal que $T(n)\in\Theta(n^2)$ todos los $T_2$ (Sugerencia: trate de restar $T_2n^2+(g_2-2T_2)n+T_2\leq T_2\cdot n^2$ desde ambos lados para ver lo que te queda). Un enfoque similar se encargará el otro lado de la desigualdad en la $n$ definición.
