Algoritmo de tiempo lineal para encontrar max desplazado

Suponga que se nos da una matriz $A[1..n]$ contiene enteros no negativos (no necesariamente distintos).

$B$$A$

La solución obvia es ordenar $A$ y luego calcular $m$ . Esto proporciona un algoritmo que se ejecuta en el tiempo $O(n \lg n)$ en el peor de los casos.

¿Es posible hacerlo mejor? ¿Podemos calcular $m$ en tiempo lineal?

Mi pregunta principal es la de arriba. Pero sería interesante saber acerca de la siguiente generalización del problema.

Deje que $B$ sea $A$ ordenados según alguna comparación Oracle $\leq$ y $f$ una función dada por un oráculo. Dados $A$ y oráculos para $\leq$ y $f$ , ¿qué podemos decir sobre el tiempo necesario para calcular $m = \max_{i \in [n]} f(B[i],i)$ ?

Todavía podemos calcular $m$ en tiempo $O(n \lg n)$ . Pero, ¿podemos demostrar un límite inferior superlineal para este caso generalizado?

Si la respuesta es sí, ¿se mantiene el límite inferior si suponemos que es el orden habitual en los enteros es una función "agradable" (monótono, polinomial, lineal, etc.)?$\leq$$f$

Podemos calcular en tiempo lineal.$m$

Para simplificar, suponga que las matrices están basadas en 0: , . Queremos calcular .B [ 0 .. n - 1 ] m = max i B [ i ] + $A[0..n-1]$$B[0..n-1]$$m = \max_i B[i]+i$

Deje . Obviamente .m a x ≤ $max = \max_i A[i]$$max \leq m$

Deje ser después de ordenar. Si tenemos B [ k ] A [ j ] ≤ m a x - n B [ k ] + k ≤ B [ k ] + ( n - 1 ) = A [ j ] + ( n - 1 ) ≤ ( m a x - n ) + ( n - 1 ) $A[j]$$B[k]$$A[j] \leq max - n$

Por lo tanto, podemos ignorar cuando . Solo necesitamos considerar los números en el rango .A [ j ] ≤ m a x - n [ m a x - n , m a x $A[j]$$A[j] \leq max - n$$[max-n, max]$

Podemos usar el orden de conteo para ordenar los números en que están en el rango en tiempo lineal y usar la lista ordenada para calcular .[ m a x - n , m a x ] $A$$[max-n, max]$$m$

Si la matriz consta de enteros distintos, entonces , ya que la distancia entre las entradas adyacentes en es al menos ; la situación es más interesante cuando no necesitan ser distintos.$A$$m = \max(A) + 1$$B$$1$

Para su pregunta más general, imagine una situación en la que solo es "interesante" cuando . Parece posible construir un argumento adverso que lo obligue a consultar para todo antes de que pueda saber , por lo tanto, necesita ordenar para encuentre la respuesta, que toma comparaciones de . (Hay algunas complicaciones ya que podría ser el caso de que podamos probar si en tiempo constante en lugar de lineal al consultar .) Este es el caso incluso si es un polinomio (de alto grado).$f(B[i],j)$$i = j$$f(B[i],i)$$i$$\max_i f(B[i],i)$$A$$\Omega(n\log n)$$A[i] = B[j]$$f(A[i],j)$$f$