S02 PsAlgorithmComplexity

Data structure and Algorithms
Thanh-Hai Tran
Electronics and Computer Engineering

School of Electronics and Telecommunications
Hanoi University of Science and Technology
1 Dai Co Viet - Hanoi - Vietnam
Outline
n Objectives and contents of the course

n Basic concepts of DS & algorithms
n Languages for expressing algorithms
n Design and Analysis of algorithms
2020 2
Analysis of algorithms
n Determine the correctness of algorithms:

u Proof by induction (Chứng minh bằng quy nạp)
u Proof by counter-example (Chứng minh bằng phản ví dụ)
n Analyzing an algorithm: determining the amount of
resources (time and memory) needed to execute it.
u Estimation of runtime
« Manual measures: using clocks (usually in programs)
« By theory: estimation of algorithm complexity (xác định độ phức
tạp của giải thuật)
u Estimation of used memory space
n Running time requirements are more critical than
memory requirements
2020 3
n An algorithm may run faster/slower and use more/less

on certain data sets than on others
n Many indicators for assessing the efficiency:
u Average case
u Best case (lower bound)
u Worst case (upper bound)
u Most common case
n How to measure complexity?
u Experimental studies
u Theoretical analysis with pseudo-code, flowcharts
2020 4
Analyses of computational times
n Experimental method
u Setting algorithm in programming language
u Run the program with different input data
u Measure program execution time and evaluate the increase
u Size relative to the size of the input data
n Limitations:
u Limitation in the quantity and quality of test samples
u Requires testing environment (hardware and software) should
be uniform, stable
2020 5
n Theoretical methods
u Able to review any input data
u Used to evaluate algorithms independent of testing
environment
u Used with high-level descriptions of the algorithm
n Implementing this method must take care of
u Language describing algorithm
u Determination of the time measurement
u An approach to generalizing time complexity
2020 6
n Measuring time used in the method of theoretical

analysis
u Basic math operation is performed with time intercepted by a
constant that is independent of data size
n Measuring the time of an algorithm is determined by
counting the number of basic operations that the
algorithm realizes
n Typical operations: assignment, function call, arithmetic

operation, array reference, return, comparison
2020 7
An example
n Line 1: 2 typical operations
n Line 2:
u Assignment i= 1 (1)
u Comparison i< n (n times)
n Inside loop (n-1) times

u One comparison + one
reference: 2(n-1)
u One assignment + one
reference: 2(n-1)
u Increase I = I +1 2(n-1)
n Line 3: a return 1 - Input datasize n

n Totally: 2 + 1 + n + 6(n-1) - Time to run a typical operation is constant
+1 = 7n - 2 - Total times of al = total number of typical
operations
n O(n)
- We compute the number of typical
operations (assignment, reference,
2020 increment, …) 8
Algorithm Efficiency
n Linear Loops: the loop updation statement either adds or

subtracts the loop-controlling variable
u for(i=0;i<100;i++) statement block;
« The efficiency is directly proportional to the number of iterations
f(n) = n where n is the number of iterations
u for(i=0;i<100;i+=2) statement block;
« the number of iterations is half the number of the loop factor f(n)
= n/2
n Logarithmic Loops: the loop-controlling variable is either
multiplied or divided during each iteration of the loop
u for(i=1;i<1000;i*=2) statement block;
u for(i=1000;i>=1;i/=2) statement block;
u How many time the loop is executed ? The efficiency f(n) =
log2(n)
2020 9
Algorithm Efficiency
n Nested Loops: Loops that contain loops are known as

nested loops
u for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some
O(1) expressions } }
« Determine the number of iterations each loop completes.
« The total is then obtained as the product of the number of
iterations in the inner loop and the number of iterations in the
outer loop
n Types of nested loops
u Linear logarithmic loop
u Quadratic loop
u Dependent quadratic loop
2020 10
Estimation of algorithm complexity
n Objective:
u Given an algorithm A with n representing its data size. We
need to find a formula (function) TA(n) that expresses the
running time of A in computers (we usually use T(n) for short).
n Normally, there are 3 cases for T(n):
u Example:
« Given an array
« Please find out the value x in the array
u Best case Tb(n): the case that algorithm can be run the most
quickly
u Worse case Tw(n): the case that algorithm can be run the
most slowly
u Average case Ta(n): the average of all cases.
2020 11
Estimation of algorithm complexity
2020 12
An example
n Sequential search algorithm: search for a value in an

array
n Worst case: n
n Best case: 1
n Average case: T(n) = ∑ 𝑖𝑝! where is pi is the probability that
value of interest appears at a[i]. When pi = 1/n the total
number will be (n+1)/2
2020 13
n Many algorithms are simply too hard to analyze

mathematically.
n There may not be sufficient information to calculate the
behavior of the algorithm in the average case.
n Big O analysis only tells us how the algorithm grows with
the size of the problem, not how efficient it is, as it does not
consider the programming effort.
n It ignores important constants.
n For example, if one algorithm takes O(n2) time to execute
and the other takes O(100000n2) time to execute, then as
per Big O, both algorithm have equal time complexity. In
real-time systems, this may be a serious consideration.
2020 14
Big O concept (ô lớn)
n Definition: Given an integer n that is not negative, and two
functions f(n) và g(n) defined in non-negative domains. We
say that:
f(n) = O (g(n)) (f(n) is big O of g(n))
if and only if there exists a constant C and n0, so that:
" n ³ n0 then f(n) £ C.g(n)
n Meaning of big O: f(n) = O (g(n)) means that for " n ³ n0
g(n) is above asymptote of f(n) (For large amounts of data,
f(n) will grow no more than a constant factor than g(n))
n Hence, g provides an upper bound.
2020 15
n c is a constant which depends on the following factors:

u the programming language used,
u the quality of the compiler or interpreter,
u the CPU speed,
u the size of the main memory and the access time to it,
u the knowledge of the programmer, and
u The algorithm itself, which may require simple but also time-
consuming machine instructions.
2020 16
Categories of algorithms
n Constant time algorithm: O(1)

n Linear time algorithm: O(n)
n Logarithmic time algorithm: O(log n)
n Polynomial time algorithm: O(nk) where k > 1
n Exponential time algorithm: O(2n)
2020 17
2020 18
Example
n Show that 4n2 = O(n3)

n Show that 400n3 + 20n2 = O(n3)
2020 19
Rules to determine complexity
n Additional rule: P1, P2 wwith corresponding T1(n), T2(n)

then
u The computational time of P1 then P2 is T1(n)+T2(n)
u The complexity could be: O(max(f(n), g(n))) where T1(n) =
O(f(n)); T2(n) = O(g(n))
n Multiplicative rule:
u The computational time of P1 in P2 is T1(n)T2(n)
u The complexity could be: O(f(n) * g(n)) where T1(n) = O(f(n));
T2(n) = O(g(n))
2020 20
Limitations of Big O Notation
n Many algorithms are simply too hard to analyze

mathematically.
n There may not be sufficient information to calculate the
behavior of the algorithm in the average case.
n Big O analysis only tells us how the algorithm grows with
the size of the problem, not how efficient it is, as it does not
consider the programming effort.
n It ignores important constants. For example, if one
algorithm takes O(n2) time to execute and the other takes
O(100000n2) time to execute, then as per Big O, both
algorithms have equal time complexity. In real-time
systems, this may be a serious consideration.
2020 21
Example
2020

S02 PsAlgorithmComplexity

Uploaded by

Copyright:

Available Formats

S02 PsAlgorithmComplexity

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

S02 PsAlgorithmComplexity

Uploaded by

Copyright:

Available Formats

Data structure and Algorithms

Electronics and Computer Engineering

n Objectives and contents of the course

n Determine the correctness of algorithms:

n An algorithm may run faster/slower and use more/less

n Measuring time used in the method of theoretical

n Typical operations: assignment, function call, arithmetic

u Comparison i< n (n times)

n Inside loop (n-1) times

n Line 3: a return 1 - Input datasize n

n Linear Loops: the loop updation statement either adds or

n Nested Loops: Loops that contain loops are known as

n Sequential search algorithm: search for a value in an

n Many algorithms are simply too hard to analyze

n c is a constant which depends on the following factors:

n Constant time algorithm: O(1)

n Show that 4n2 = O(n3)

n Additional rule: P1, P2 wwith corresponding T1(n), T2(n)

n Many algorithms are simply too hard to analyze

You might also like