Complejidad Logaritmica ( Java 2)
-
Upload
ximena-itzel-garcia-diaz -
Category
Documents
-
view
15 -
download
1
description
Transcript of Complejidad Logaritmica ( Java 2)
-
2. Calcula la complejidad de los siguientes algoritmos:
2.1. i = 1
Mientras (i
-
Ahora, notamos que el bucle se lleva a
cabo 2 ITERACIONES =log2n porque en el bucle
valor de i se dobla en cada iteracin, de este
modo podemos determina una eficiencia
f2(n)= log2n y una complejidad del bucle
interno O(f2(n))= log2n
Por lo tanto, como el cdigo es un bucle anidado, entonces la
complejidad del cdigo es:
O(n)=O(f1(n))* O(f2(n))=n*log2n= nlog2n.
(Sabemos: log2n< n< nlog2n< n2)
O(n)= nlog2n
j j=j*2
1 1
2 2
3 4
4 8
5 16
6 32
7 64
8 128
9 256
10 512
11 1024
12 2048 . . .
.
.
. n-1 j=(j-
1)*2
n j=j*2
-
2.2. i = 1
Mientras (i
-
Y notamos que el nmero de iteraciones es
directamente proporcional al recorrido
hasta 10 del bucle, entonces, tenemos una
funcin de eficiencia constante f2(n) = 10.
Por lo tanto, la complejidad del bucle
externo es O(f2(n))=O(1)=1 por ser
constante.
Por lo tanto, como el cdigo es
un bucle anidado, entonces la complejidad
del cdigo es:
O(n)=O(f1(n))* O(f2(n))=O(n2-1)*O(1)= n2*1=n2.
O(n)=n2.
j j=j+1
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10