¿Cuáles son los pasos para calcular la complejidad del algoritmo?

Answer 1

En el ejemplo que dio, el “paso” que consideraríamos sería “arr [index] == sValue” y se repite la longitud de la matriz – 1 vez. Si la longitud de la matriz es n, es del orden de O (n-1) que es igual que O (n).

Básicamente, consideramos un “paso” que es el que más tiempo consume, se repite en nuestro algoritmo y vemos cuántas veces lo estamos ejecutando.
El paso que seleccionamos para un algoritmo puede ser diferente del paso que elegimos para otro.
Esa es la razón por la que optamos por medidas asintóticas de estos pasos (cuando el tamaño de entrada alcanza el infinito). Cuando hablamos en términos asintóticos, O (n) y O (n + 1) están tan cerca que decimos que son lo mismo. Pero no son iguales a O (N ^ 2), independientemente del tiempo tomado por los pasos que consideramos (n, N), cuando n, N alcanzan el infinito, O (n ^ 2) será mayor que O (N).

Obtendrá una muy buena comprensión de cómo funcionan las notaciones asintóticas de esta página “8” (no 30) pdf 🙂 http://classes.soe.ucsc.edu/cmps…

Answer 2

Puede leer acerca de los pasos básicos: Determinar la complejidad de un algoritmo: Lo básico

Answer 3

1. ¿Multiplico el tiempo necesario para cada paso o los sumo?
Respuesta: Los sumas.

2. Para una comparación no es posible determinar cuándo terminará. Entonces, ¿qué es el tiempo empleado? (Asumí 1 porque se puede encontrar en el primer índice, N de lo contrario como último índice)
Respuesta: Será 1 y se repetirá con la cantidad de elementos de la matriz en su caso.

3. ¿Las asignaciones y devoluciones son tiempo constante 1?
Respuesta: Sí, se cuentan como 1.