¿Cómo determinar el tiempo de ejecución de peor caso de cada programa utilizando la notación de gran O? [duplicado] - algoritmo, tiempo de ejecución, matemáticas discretas

Estoy teniendo problemas para entender esta pregunta y cómo llegar a la respuesta. Cómo calcular ¿El peor caso de ejecución?

La entrada de los siguientes programas es una matriz A que contiene n enteros A [1] · · · A [n]. Limite el tiempo de ejecución de cada programa en el peor de los casos utilizando notación big-O.

Problema 1:

i = 1, total = 0
while i < n/2:
total = total + A[i]
i=i*2

Problema 2:

total = 0
S = the set {1,2,3,4...n}
for each subset T of S
for each element x in T
total = total + A[x]

Problema 3:

int i = 1, j = 1;
for i = 1 to n:
while (j < n && A[i] < A[j])
j++

La suma del prefijo de una matriz de números A [1],. . . , A [n] es una segunda matriz B [1],. . . , B [n] donde

B [i] = suma de j = 1 a i A [j]

Los siguientes problemas calculan la suma del prefijo:

Problema 4:

for i = 1 to n:
B[i] = 0;
for j = 1 to i:
B[i] += A[j]

Problema 5:

B[1] = A[1];
for i = 2 to n:
B[i] = B[i-1] + A[i]

Respuestas

1 para la respuesta № 1

Problema 1:
El algoritmo realiza una operación de tiempo constante (adición) en el punto de cada acceso, y ese acceso se realiza mientras i<n/2. Ya que i se duplica cada vez, la condición ya no se mantendrá después de log(n/4) pasos, por lo que el peor caso es la complejidad del tiempo O (log (n)) (logarítmica).

Problema 2:
El algoritmo accede a cada elemento de la matriz (x en pseudocódigo) tantas veces como está en un subconjunto de S, y realiza una operación de tiempo constante en el punto de acceso. Cada elemento esta en 2 ^ (n-1) subconjuntos que se contienen, y hay norte Tales elementos, por lo que el peor caso es la complejidad del tiempo O (n * 2 ^ (n)) (exponencial).

Problema 3:
Observe que cada vez que se comprueba la condición en el bucle while, el valor de i+j aumenta por 1, y el valor de i+j nunca puede disminuir Ya que i+j empieza a 2 y nunca puede ir más allá 2n+1, la complejidad global del algoritmo es O (n) (lineal).

Problema 4:
Para un valor dado de i, el bucle interno corre i veces. Promover, i varía de 1 a n, por lo que realizamos 1 + 2 + 3 + ... + n = n (n + 1) / 2 cálculos de tiempo constante (adiciones), por lo que la complejidad general del algoritmo es O (n ^ 2) (cuadrático).

Problema 5:
El algoritmo accede. n-1 elementos de la matriz, y realiza una operación de tiempo constante en el punto de cada acceso (adición), por lo que la peor complejidad de tiempo es O (n) (lineal).

---