Cualquier idea de cómo transformar este O (n^2) algo en un O (n)

Question

Tengo el siguiente algoritmo que escanea una gran matriz circular (datos). En cierto punto de la matriz, necesito echar un vistazo a los valores pasados ​​(0 = el punto de datos más nuevo, n = el punto de datos más antiguo) y determinar si hubo un valor 5% por debajo del valor actual. Terminé escribiendo un algoritmo O (n^2) que funciona bien, pero no escala.

 const int numberOfDataPointsInPast = 1000; 
     int numberOfDataPoints = 0; 
     for (int i = numberOfDataPointsInPast; i >= 0; i--) 
     { 
      double targetPoint = data[i] * 0.95; 
      for (int j = i + numberOfDataPointsInPast; j > i; j--) 
      { 
       if (data[j] <= targetPoint) 
       { 
        numberOfDataPoints++; 
        break; 
       } 
      } 
     } 

alguna idea de cómo podría transformar esto en un (n) algo O? ¡Gracias!

Answer 1

Al iterar la matriz almacenar el valor más bajo. Esto requiere crear una variable mínima y realizar una comprobación de comparación en cada paso. En lugar de comparar todos los valores anteriores con el nuevo, compárelo solo con el más bajo.

Answer 2

EDIT:

Después de pensarlo somemore, un algoritmo fácil a la hora de O (n) es posible, sin necesidad de RMQ o árbol (véase la parte anterior de mi respuesta a continuación).

Dada una matriz A [1 ... n] y un ancho de ventana W, necesita encontrar el mínimo A [i, ... i + W], dado i.

Para esto, haz lo siguiente.

Dividir A [1 ... n] en bloques contiguos de tamaño W-1. B1, B2, ... B (W-1).

Para cada bloque B, mantenga dos bloques más llamados BStart y BEnd.

BSinicio [i] = mínimo de B 1, B [2], ..., B [i].

BEnd [i] = mínimo de B [W-1], B [W-2], ..., B [W-i].

Esto se puede hacer en tiempo O (W) para cada bloque y, por lo tanto, O (n) tiempo total.

Ahora dado un i, la sub-matriz A [i ... i + W] abarcará dos bloques consecutivos, digamos B1 y B2.

Encuentra el mínimo de i al final del bloque B1, y comienza del bloque B2 a i + w usando B1End y B2Start respectivamente.

Esto es O (1) tiempo, tan total O (n).

Para un conjunto circular C [1 .... n], todo lo que necesita hacer es ejecutar lo anterior en

A [1 .... 2n], que es básicamente dos copias de C concatenan juntos, es decir, A [1 ... n] = C [1 ... n] y A [n + 1 ... 2n] = C [1 ... n]

---

writeup Anterior.

Ok. Suponiendo que haya entendido su pregunta correctamente esta vez ...

Es posible en el tiempo O (n) y en el espacio O (n).

De hecho, es posible cambiar el tamaño de su ventana a cualquier número que desee, tenerlo diferente para diferentes elementos y seguir funcionando!

Dado un conjunto A [1 ...n], puede preprocesarse en O (n) tiempo y O (n) espacio para responder consultas de la forma: What is the position of a minimum element in the sub-array A[i...j]? en constante tiempo!

Esto se conoce como el problema Range Minimum Query.

De manera teórica, es posible hacerlo en el tiempo O (n).

El solo uso de un árbol le dará O (nlogW) tiempo, donde W es el tamaño de la ventana y probablemente funcionará mucho mejor que RMQ, en la práctica, ya que supongo que las constantes ocultas empeorarán la RMQ.

Puede usar un árbol de la siguiente manera.

Comience hacia atrás e inserte elementos W. Encuentra el mínimo y presiona sobre una pila. Ahora borre el primer elemento e inserte (W + 1) el elemento th. Encuentra el mínimo, empuja en la pila.

Continúe de esta manera. El tiempo total de procesamiento será O (nlogW).

Al final tiene una pila de mínimos, que puede seguir apareciendo mientras camina por la matriz una segunda vez, esta vez en el orden correcto, buscando 0.95 * objetivo.

Además, su pregunta no es muy clara, usted dice que es un búfer circular, pero parece que no está haciendo una operación de módulo con la longitud. Y como está codificado, su algoritmo es O (n), no O (n^2) ya que el tamaño de su ventana es una constante.

Answer 3

No creo que sea posible hacerlo en O (n) porque al resolverlo con O (n) puede ordenarlo con O (n) y eso no es posible. (mínimo, para ordenar es O (nlogn)).

EDITAR - reducir la clasificación a este problema

supongamos que puede decir para cada punto de la cantidad de puntos en el pasado tiene un valor menor que x% (en este caso x es 5 - pero X también puede ser 0, entonces el contará cualquier punto más pequeño en el pasado).

Ahora, supongamos que desea ordenar una matriz de n elementos.
Si puede obtener el número de puntos más pequeños en el pasado para todos los elementos en O (n) si el punto a tiene un valor mayor que el punto b, el recuento del punto a también será mayor que el punto b (porque matriz es circular). Entonces, este problema en realidad produce una función desde los valores hasta el conteo que preserva el orden.
Ahora - los nuevos valores están enlazados entre o y n y esto puede ser ordenado en el tiempo n.

Corrígeme si me equivoco (podría ser que no entendí el problema en primer lugar).

Answer 4

Puede tomar el primer numberOfDataPointsInPast en el pasado ordenarlos, que es n log (n). Luego haga una búsqueda binaria, log (n), encuentre el punto de datos más bajo que pase la prueba del 5%. Eso le indicará cuántos puntos del número de puntos de datos introducidos pasará la prueba en n log (n) de tiempo, creo.

Answer 5

Puede mantener una matriz buffArray para numberOfDataPointsInPast elementos que contendrán los elementos de "ventana" actuales ordenados en orden ascendente.

Para cada iteración:

• Comprobar si el elemento actual es menor que 0.95 * buffArray[0] y llevar a cabo las acciones necesarias si lo es.
• Eliminar elemento que sale de "ventana" (es decir, i+numberOfDataPointsInPast 'th) desde buffArray.
• Agregar nuevo elemento (es decir, i 'th) a buffArray manteniendo el orden de clasificación.

Esto no es O (N) como yo entiendo, pero definitivamente más efectivo que O (N^2) ya que agregar y quitar elementos a/de matriz ordenada es O (log N). Sospecho que la eficiencia final es O (N log (W)), donde W es numberOfDataPointsInPast.

Answer 6

Creo que entiendo sus necesidades .... voy a replantear el problema:

Dada: un tamaño de búfer deslizante K, y una matriz de datos de tamaño N> K, los índices de 0 a N-1.

Compute: Contar el número de puntos j tales K < = j < N-1, y que el conjunto {datos [j-1], datos [j-2], datos [j-3], ... data [jK]} contiene al menos un punto que tiene un valor de < = 0.95 * datos [j].

Esto se puede lograr de la siguiente manera:

1. Ordenar los puntos {datos [0], de datos [1], ... de datos [K-1]} utilizando una estructura de datos que tiene a lo sumo Costo O (log N) para inserción/remoción.

2. Inicialice un contador de R a 0, inicializar j a K.

3. Comprobar la matriz ordenada para ver si el punto más bajo es < = datos [j] * 0.95; en caso afirmativo, incremente R.

4. Elimine los datos [j-K] de la matriz ordenada e inserte datos [j] en la matriz ordenada.

5. Incremento j

6. Si j < N, volver al paso 3.

La clave aquí es elegir la estructura de datos adecuada. Estoy bastante seguro de que un árbol binario funcionaría. Si el costo de inserción incremental es O (log N), entonces su tiempo de ejecución total es O (N log N).

Answer 7

Las iteraciones deben comenzar desde abajo e incrementarse (manteniendo el mínimo del pasado). En este momento, según lo publicado, el algoritmo siempre está mirando hacia atrás, en lugar de avanzar y recordar el mínimo anterior.

A medida que se agregan nuevos puntos, el rango de puntos de datos solo puede aumentar el límite superior o inferior. A medida que el límite inferior disminuye, mantener el límite inferior es todo lo que es necesario. Cualquier punto nuevo que sea más que el límite inferior/0.95 será aceptable (ya que el límite inferior es siempre en el pasado):

const int numberOfDataPointsInPast = 1000; 
int numberOfDataPoints = 0; 
double lb = NAN; 
for (int i = 0; i < numberOfDataPointsInPast; i++) 
{ 
    if (lb == NAN || data[i] < lb) { 
     lb = data[i]; 
    } 
    if (data[i] >= lb/0.95) { 
     numberOfDataPoints++ 
    } 
} 

Answer 8

Prueba esto:

mantener siempre dos punteros a elementos dentro de su memoria intermedia. Uno es el valor mínimo encontrado y el otro es el siguiente mimumum (que es el próximo más alto por incremento). Recuerde que estos son punteros en el búfer.

En cada paso en su progresión a través del búfer, determine si el valor actual es menor o igual que el valor señalado por min1 o min2, de ser así, actualice min1 o min2 para señalar a la ubicación actual. De lo contrario, si la aritmética del puntero, el valor de min1 o min2 es 1500 lugares en el búfer, debe determinar cuál es y reajustar min1 o min2 en consecuencia, es decir, min1 puntos a min2 y min2 está configurado para señalar en la ubicación actual, o min2 simplemente se configura para que apunte a la ubicación actual.

Si el valor apuntado por cualquiera min-1 o mín2 es inferior al 15% del valor actual, entonces se puede determinar por simple comparación ...

Answer 9

Usted tiene dos opciones:

1. Ordenar es - O (n log n)

2. Median of Medians algorithm