Al informar la complejidad de tiempo asintótica, ¿puede una variable dominada sobre otros?

Question

Quiero expresar la complejidad del tiempo asintótico para el peor de los casos de clasificar una lista de $ n $ cadenas, cada cadena de longitud $ k $ letras. Usando Ferge-Sort, Ordenar una lista de $ n $ elementos requiere $ o (n \ log n) $ . Comparando dos cadenas de longitud $ k $ tiene un costo de $ o (k) $ . Por lo tanto, el costo sería $ o (kn \ log n) $ .

Sin embargo, conozco algunas restricciones sobre $ k $ y $ n $ debido a la naturaleza de el problema. En particular, lo sé para cualquier lista, $ 0 \ lt k \ leq 20 $ , y $ 0 \ lt n \ leq 80000 $ . En otras palabras, el número de palabras en una lista puede variar en un rango mucho más grande que la longitud de las palabras.

En ese caso, ¿sería correcto decir que $ n $ domina sobre $ k $ Y, por lo tanto, el costo podría expresarse como $ o (n \ log n) $ ? ¿O el hecho de que estamos discutiendo los costos asintóticos con esas restricciones sin sentido (ya que estamos describiendo cómo el algoritmo se ve afectado por el crecimiento de cada variable, independientemente de cuánto puedan crecer realmente)? En general, si dos variables son independientes, ¿es posible despedir a uno de ellos del costo asintótico bajo ciertas circunstancias?

Answer 1

En primer lugar, si $ k $ y $ n $ están limitados, todas las complejidades trivializan $ o (1) $ .Por lo tanto, una mejor suposición es algo así como $ k= o (\ log n) $ .Bajo este supuesto, puede, por ejemplo, decir que $ o (k + n)= o (n) $ , e incluso $ O (k + \ log n)= O (\ log n) $ .Sin embargo, usted no puede decir que $ O (kn)= o (n) $ , ¡ya que no es necesariamente cierto!Si $ k=log n $ , entonces no es cierto que $ O (kn)= o (n) $ .En su lugar, todo lo que puede decir es que $ O (kn)= o (n \ log n) $ .