Red de conocimiento informático - Aprendizaje de código fuente - Complejidad temporal de los algoritmos de estructura de datos

Complejidad temporal de los algoritmos de estructura de datos

Según las convenciones analíticas, se supone que la complejidad temporal de todas las operaciones individuales es 1

x=n; ...1

mientras(xgt;=(y 1)* ( y 1))...4 (2 sumas, 1 multiplicación, 1 comparación)

y=y 1...1

Complejidad del tiempo = 1 (4 1) x Número de bucles

El número de bucles está determinado por los valores iniciales de n e y. Supongamos que el número de ciclos es N, el valor inicial de y es y0 y el estado final de y es yn, entonces existe

x lt; (yn 1)*(yn 1). Supongamos que y El valor inicial es un número entero, entonces yn es el número entero más pequeño que satisface esta ecuación

N = (yn - y0) / 1... Dado que y se incrementa en 1 cada vez que pasa. bucle

La fórmula 1 se simplifica a x = (yn 1)*(yn 1), por lo que podemos obtener yn = n^(1/2) - 1

Entonces N = n ^(1/2) - 1 - y0

Usando la notación O grande y considerando solo los términos de orden más alto, la complejidad de resolver N es O(n^(1/2))

Continuar buscando

La complejidad total de 3 líneas de código = 1 (4 1) x O(n^(1/2))

La complejidad del tiempo total es O (n^(1/ 2)), ya que los términos constantes conocidos y los términos que no son de orden superior generalmente se ignoran (en el espíritu de Big O)