Supongamos que tengo un 2-la función de variable $g(k,n)$, y sé que $g(k,n)=O(n^{f(k)})$, fija $k$$n \rightarrow \infty$, para alguna función $f=f(k)$. Supongamos también sé que $f(k)=O(\log k)$.
Es legítimo escribir $g(k,n)=O(n^{O(\log k)})$?
Respuestas
¿Demasiados anuncios?
En este caso particular, se puede simplificar y a la conclusión de que $g(k,n) = n^{O(\log k)}$, ya que se puede poner doble la primera constante en el segundo (mientras $n,k \geq 1 + \epsilon$). Esta falla si usted piensa de $n$ como tendiendo a infinito, sino $k$ podría ser arbitrariamente cerca de $1$.
EDIT: Mi respuesta se supone que la constante en $g(k,n) = O(n^{f(k)})$ no depende de k, que es la convención habitual en ciencias de la computación. Si lo hace, nos gustaría escribir $g(k,n) = O_k(n^{f(k)})$ a enfatizar este (o, a veces sólo destacar que en palabras).
Matt Dawdy
Puntos
5479
No (si te refieres a lo que creo que quieres decir con esa afirmación). Si usted tiene más de una variable en juego es siempre una buena idea para hacer un seguimiento de las variables implícitas constante para cada uno de los grandes-O depende. En tu ejemplo, la implícita constante para el exterior big-O depende de $k$, pero las constantes en el interior de la grande-O no, por lo que parece engañoso utilizar la notación que se pretende son los mismos. Y si el implícita constante crece lo suficientemente rápido, la declaración final que desea es falsa (si un unadormed big-O significa que no depende de ninguna de las variables que aparecen en el lado izquierdo). Considere la posibilidad de que, como dije en mi comentario para Yuval Filmus, $g(k, n) = 2^k n^{\log k}, f(k) = \log k$. Además de a $f(k) = O(\log k)$ usted necesita saber que la implícita constante no depende de $n$.
Edit: El de arriba era una tontería. En realidad está bien. Usted tiene una constante de $C_1$ tal que $f(k) \le C_1 \log k$ y otro constante $C_2$ tal que $g(k) \le C_2 n^{f(k)}$, por lo tanto $g(k) \le C_2 n^{C_1 \log k}$, o como Yuval Filmus señala, $g(k) = n^{O(\log k)}$.
