PowerPoint Presentation
*
Algorithm Efficiency
To design and implement algorithms, programmers
must have a basic understanding of what
constitutes good, efficient algorithms. In this
section we discuss and develop several principles
that are used to analyze algorithms.
Linear Loops
Logarithmic Loops
Nested Loops
Big-O Notation
Standard Measurement of Efficiency
*
Algorithm efficiency is generally defined as a function of the numbers to be processed.
The simplification of efficiency is known as
big-O notation.
*
As n grows large, the n2 term will come to dominate, so that all other terms can be neglected.
Further, the constants will depend on the precise details of the implementation and the hardware it runs on, so they should also be neglected.
Big O notation captures what remains: we write O(n2) and say that the algorithm has order of n2 time complexity.
*
Data Structures: A Pseudocode Approach with C, Second Edition
*
Data Structures: A Pseudocode Approach with C, Second Edition
*
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
. . .
2n = x
*
20 = 1 log2 1 = 0
21 = 2 log2 2 = 1
22 = 4 log2 4 = 2
23 = 8 log2 8 = 3
24 = 16 log216 = 4
. . .
2n = x log2x = n
*
20 = 1 log2 1 = 0
21 = 2 log2 2 = 1
22 = 4 log2 4 = 2
23 = 8 log2 8 = 3
24 = 16 log216 = 4
. . .
2n = x log2x = n
*
20 = 1 log2 1 = 0
21 = 2 log2 2 = 1
22 = 4 log2 4 = 2
23 = 8 log2 8 = 3
24 = 16 log216 = 4
. . .
2n = x log2x = n
log240 = ?
*
20 = 1 log2 1 = 0
21 = 2 log2 2 = 1
22 = 4 log2 4 = 2
23 = 8 log2 8 = 3
24 = 16 log216 = 4
. . .
2n = x log2x = n
5 = log232 < log240 < log264 = 6
*
2. Give the BigO notation for each of the following pseudocode fragments:
(A) a = n
b = n + 1
*
2. Give the BigO notation for each of the following pseudocode fragments:
(A) a = n
b = n + 1
Answer: constant ( or O(1) )
*
2. Give the BigO notation for each of the following pseudocode fragments:
(B) a = n
if( a >= 0 )
b = n + 1
else
b = (-1)*n + 1
end if
*
2. Give the BigO notation for each of the following pseudocode fragments:
(B) a = n
if( a >= 0 )
b = n + 1
else
b = (-1)*n + 1
end if
Answer: O(1)
*
2. Give the BigO notation for each of the following pseudocode fragments:
(C) i = 1
loop( i <= n )
print( i )
i = i + 1
end loop
*
2. Give the BigO notation for each of the following pseudocode fragments:
(C) i = 1
loop( i <= n )
print( i )
i = i + 1
end loop
Answer: O(n)
*
2. Give the BigO notation for each of the following pseudocode fragments:
(D) i = n
loop( i > 0 )
print( i )
i = i – 1
end loop
j = 1
loop( j <= n )
print( j )
j = j + 2
end loop
*
2. Give the BigO notation for each of the following pseudocode fragments:
(D) i = n
loop( i > 0 )
print( i )
i = i – 1
end loop
j = 1
loop( j <= n )
print( j )
j = j + 2
end loop
Answer: n + n/2 => O(n)
*
Calculate the run-time complexity of the following algorithm segment:
i = 1
loop( i <= n )
j = 1
loop( j <= n )
k = 1
loop( k <= n )
print( i, j, k )
k = k + 1
end loop
j = j + 1
end loop
i = i + 1
end loop
*
i = 1
loop( i <= n )
i = i + 1
end loop
j = 1
loop( j <= n )
j = j + 1
end loop
k = 1
loop( k <= n )
print( i, j, k )
k = k + 1
end loop
Answer: n · n · n => O(n3)
*
(E) i = 1
loop( i <= n )
print( i )
i = i * 2
end loop
*
*
(E) i = 1
loop( i <= n )
print( i )
i = i * 2
end loop
Answer: O(log2n)
*
(F) i = n
loop( i > 0 )
print( i )
i = i / 2
end loop
j = 1
loop( j <= n )
print( j )
j = j + 2
end loop
*
(F) i = n
loop( i > 0 )
print( i )
i = i / 2
end loop
j = 1
loop( j <= n )
print( j )
j = j + 2
end loop
Answer: log2n + n => O(n)
)
(
2
n
O
2
)
1
(
)
(
+
=
n
n
n
f