desplazamiento - operadores de bits java

Java-¿Gran manipulación de bits?

Question

¿Cuál es la gran O de este código? Sé que todas las líneas son O (1), excepto la parte de recursión. No estoy seguro de cuál es la gran O de la recursión, tengo la sensación de que todavía es O (1) ya que no tenemos líneas que sean peores que O (1), pero generalmente la recursión es O (n).

Código:

public int getSum(int a, int b) {
if (b == 0){
return a;
}
if (a == 0){
return b;
}
int add = a ^ b;
int carry = (a&b) << 1;
return getSum(add, carry);
}

Editar: Esto no es tarea para el caso, es para prepararme para las entrevistas.

Answer 1

Cuando intenta analizar la complejidad de un algoritmo recursivo, a menudo ayuda encontrar la forma en que el "tamaño" de las entradas disminuye con el tiempo. Por ejemplo, si está analizando una implementación factorial recursiva, probablemente notará que el tamaño de la entrada cae en uno en cada llamada, luego use eso para decir que hay O (n) llamadas totales y por lo tanto ese O (n) el trabajo total está hecho.

Esta función recursiva es un poco difícil de analizar porque no está del todo claro qué cantidad está disminuyendo con el tiempo. El valor de los argumentos primero y segundo ambos puede aumentar a medida que se ejecuta la función, lo que generalmente no es bueno cuando se usa recursividad.

Sin embargo, hay una observación útil aquí. Mire el valor del segundo argumento para la función recursiva. Se vuelve a calcular cada vez que

b = (a & b) << 1

que tiene un efecto muy interesante: el número de 0 bits al final de la representación binaria de b aumenta en al menos uno en cada llamada de función. Para ver esto, imagine que b termina con k 0 bits. La computación de a & b producirá un número cuyos últimos k bits son cero, y luego al desplazar el resultado en un paso aumentará el número de ceros a la derecha en uno.

Al mismo tiempo, el algoritmo terminará cuando el número de 0 más a la derecha en la representación binaria de b exceda la posición del extremo izquierdo 1 en la representación binaria de a. Para ver por qué, tenga en cuenta que mantenemos ANDing b con a, y tan pronto como los 1 bit en b superan los 1 bit en a, AND evalúa a 0 y se desencadena el caso base.

Al unir esto, podemos ver que la cantidad de llamadas recursivas realizadas está limitada por la posición del bit 1 más alto en el número a, ya que cada iteración mueve los 1 bits en b cada vez más alto y la recursión se detiene cuando esos 1s pasan el 1s en a.

Entonces, ahora la pregunta es qué significa eso desde una perspectiva de gran O. Si tiene un número ny escribe n en binario, la posición del bit 1 más alto en n es O (log n), ya que el significado de ese bit crece exponencialmente en función del tiempo. Por lo tanto, el tiempo de ejecución aquí es O (log n), donde n es el máximo de las dos entradas.

Answer 2

Esta función es en realidad O(n) peor caso. Como se discutió en los comentarios anteriores, la notación O grande hace referencia al límite superior asintótico de la función. El límite superior de esta función en el peor de los casos es que cada uno de sus números de entrada es un max int . Eso significa que la función se llama una cantidad de veces igual a la cantidad de bits en un entero. Si su número entero tiene 32 bits , entonces la función se ejecuta 32 veces , cada vez ejecutando una serie de operaciones constantes. Eso hace que la función O(n) , donde n es el tamaño de su número entero.

Answer 3

Interpretaría n como el número de bits a la izquierda de, e incluido, el más a la derecha de 1 bit del valor b . A medida que n crece, también lo hace la cantidad de iteraciones recursivas posibles. En esa luz, la complejidad es O (n).

Answer 4

Primero déjame citar Wikipedia :

La notación Big O es una notación matemática que describe el comportamiento limitante de una función cuando el argumento tiende hacia un valor particular o infinito.

En ciencias de la computación, la notación O grande se usa para clasificar algoritmos de acuerdo con la forma en que aumentan los requisitos de tiempo de uso o de espacio a medida que crece el tamaño de la entrada .

Usted pregunta si el rendimiento es O (n) . Bueno, antes de que podamos responder eso, ¿qué es n ?

Como puede ver arriba, n generalmente se define como el tamaño de la entrada. Aunque eso generalmente se refiere al número (conteo) de entradas, en este caso, eso podría definirse como la magnitud de b , entonces la pregunta es: ¿El tiempo de procesamiento (es decir, el número de recursiones) aumenta a medida que se aumenta y / o cuando b aumenta?

La respuesta es no. No existe una correlación entre la magnitud de b y el número de recursiones. Claro, el número de recurrencias varía, pero no está relacionado con el tamaño .

Si n es a o b , tiene O _min (1), O _avg (6.24) y O _max (33).

ACTUALIZAR

Sin embargo, no puede obtener 33 iteraciones con valores bajos de b . El número de iteraciones está limitado por la longitud de bits de la entrada más grande. La longitud del bit sería log ₂ (n), que da la respuesta:

O (log n) donde n = max(a, b)

Answer 5

Si analizamos su función, encontramos lo siguiente:

• Si uno de los dos enteros que se le pasa es un cero -> se invocará una sola vez por la declaración de devolución al principio.

• Si los enteros pasados ​​son similares incluso si no son ceros -> se invocarán una sola vez . Esto se debe al XOR o ^ que requiere que los dos bits correspondientes sean diferentes . Por ejemplo:

  (decimal) (binary) (decimal) (binary)
  5 = 101 1 = 001
  6 = 110 1 = 001
  ********************** Whereas *********************
  3 = 011 0 = 000

• Si los enteros pasados no son ceros y no son similares -> eso llevará el programa a la parte de acarreo y aquí debemos considerar lo siguiente:

  1. Si los dos enteros no tienen bits correspondientes correspondientes -> (a&b) será igual a cero , por lo tanto, el método se invocará solo una vez . Por ejemplo:

     (decimal) (binary) (decimal) (binary)
     1 = 001 1 = 001
     2 = 010 3 = 011
     ********************** Whereas *********************
     0 = 000 1 = 001

  2. Si (a&b) resulta sin cero -> aquí llegamos a la parte de cambio << y aquí está la trama. Si pasan TODAS las condiciones anteriores -> entonces tenemos un cambio máximo de 32 bits y suponiendo que después de cada turno se produce la recursión -> tenemos un máximo de 32 recursivas PERO NO siempre. Eso significa que no podría ser el caso todas las veces (¡a veces no habría recurrencia como mostré arriba!).

Entonces, creo que es O(1) u O(n) , y si analizamos ambos casos encontramos:

• O(1) significa complejidad constante , por ejemplo:

  1 invocation : 1 second
  10 invocation : 1 second
  100 invocation: 1 second
  And so on..

  ¡Pero ese no es el caso, como mostré arriba, porque cada entrada puede causar una recursión y puede que no ! Y la recursión no es la misma, aunque el máximo es 32 pero puede estar entre 0 y 32 .

• O(n) significa una complejidad lineal , por ejemplo:

  1 invocation : 1 second
  10 invocation : 10 seconds
  100 invocation: 100 seconds
  And so on..

Concluyo Cuanto más recursividad sucede, más tiempo toma .

Sin embargo, todavía estoy abierto a la corrección.