CS计算机代考程序代写 data structure AI algorithm INN701 Lecture 1

INN701 Lecture 1

Queensland University of Technology
CRICOS No. 00213J

CAB301 Algorithms and Complexity

Lecture 2: Analysis of Algorithms

Maolin Tang
School of Computer Science

Queensland University of Technology

CRICOS No. 00213J

a university for the worldreal R

Aims of this lecture

• To introduce two ways of analysis of algorithms
– Theoretical algorithm analysis
– Empirical algorithm analysis

2

CRICOS No. 00213J

a university for the worldreal R

References

• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Pearson, third edition, 2012. Sections 2.1, 2.2(O-notation only), 2.3
and 2.6, and Appendix A

3

CRICOS No. 00213J

a university for the worldreal R

Analysis of algorithms

• In computer science, analysis of algorithms is to measure the
efficiency of algorithms.

• There are two ways to measure the efficiency of algorithms
– Theoretical analysis
– Empirical analysis

4

CRICOS No. 00213J

a university for the worldreal R

Procedure of theoretical analysis of the
efficiency of an algorithm

1. Decide on the parameter(s) characterising the size of input
2. Identify the algorithm’s basic operation
3. Set up a summation formula for the number of times the basic

operation is performed in the worst scenario
4. Solve the summation formula using standard arithmetic rules

– The result is either an exact efficiency equation or identification
of the algorithm’s efficiency class in big-O notation

5

CRICOS No. 00213J

a university for the worldreal R

Size of input

• The input size depends on the data structures involved
• When dealing with compound data structures it is usually the

number of components:
– The number of items in an array
– The dimensions of a matrix
– The number of nodes or edges in a graph

• Sometimes the input size is defined by two or more parameters to
an algorithm
– The two dimensions of a matrix
– The number of nodes and the number of edges in a graph

6

CRICOS No. 00213J

a university for the worldreal R

Basic operation

• A basic operation is an operation have the most influence on the
algorithm’s total computation time:
– Key comparisons in a searching algorithm
– Numeric multiplications in a matrix multiplication algorithm
– Visits to nodes (or edges) in a graph traversal algorithm

• A basic operation may occur in more than one place in an algorithm

7

CRICOS No. 00213J

a university for the worldreal R

Example: Maximum and minimum values

ALGORITHM MaxMin2(A[0..n − 1], MaxValue, MinValue)
// Finds the maximum and minimum numbers in an
// array A of n numbers, where n ≥ 1
MaxValue ← A[0]
MinValue ← A[0]
for i ← 1 to n − 1 do

if A[i] > MaxValue
MaxValue ← A[i]

else
if A[i] < MinValue MinValue ← A[i] 8 CRICOS No. 00213J a university for the worldreal R Example: Maximum and minimum values • Input size: The length n of array A • Basic operation: Comparison of a value with a number in the array – This basic operation appears in two places, ‘A[i] > MaxValue’ and
‘A[i] < MinValue’ • The algorithm can perform different numbers of basic operations at each iteration 9 CRICOS No. 00213J a university for the worldreal R Example: Maximum and minimum values • The worst case is when the first array element A[0] contains the largest number in the array, because this means the second if statement is always performed – In this situation the basic operation is performed twice for each iteration of the for loop – Thus the algorithm’s worst-case efficiency function is: 1 1 1 1 ( ) 2 2 1 2( 1) 2 2 n n worst i i C n n n − − = = = = = − = −∑ ∑ 10 CRICOS No. 00213J a university for the worldreal R Some frequently-used summation manipulation rules cai i=l u ∑ = c ai i=l u ∑ (ai ± bi ) i=l u ∑ = ai i=l u ∑ ± bi i=l u ∑ 1 i=l u ∑ = u − l +1, l ≤ u i i=1 n ∑ = n(n +1) 2 ≈ 1 2 n2 ik i=1 n ∑ ≈ 1 k +1 nk+1 11 Textbook - Appendix A CRICOS No. 00213J a university for the worldreal R Big-O notation • Let O(g(n)) be a class of all functions that are bounded from above by some multiple c of g(n), for ‘large’ values of n • If some function t(n) is in the class O(g(n)) then its worst-case behaviour is bounded by a function with the same ‘shape’ as g(n) • For example: – t(n) = 4n2 + 21n + 100 ∈ O(n2) – We can formally prove this by showing that 8n2 ≥ 4n2 + 21n + 100 for any n ≥ 9 12 CRICOS No. 00213J a university for the worldreal R Big-O notation 13 CRICOS No. 00213J a university for the worldreal R Big-O notation • Big-O classes ignore fine detail such as multiplicative constants, bases of logarithms and low-order terms in polynomials • Nevertheless, they are sufficient to distinguish acceptable algorithms from unacceptable ones – An O(n) algorithm will outperform an O(n2) on average for large inputs – An O(2n) algorithm will never work on large inputs 14 CRICOS No. 00213J a university for the worldreal R Example: Maximum and minimum values • The efficiency of the algorithm in big-O notation: ( ) 2 2 ( )worstC n n O n= − ∈ 15 CRICOS No. 00213J a university for the worldreal R From efficiency function to big-O notation • 4n2 + 2n - 100 ∈ O(n2) • 400n2 ∈ O(n2) • 0.01n2 ∈ O(n2) • 3n3 + 5n2 - n + 10 ∈ O(n3) • 2n + 100 ∈ O(n) 16 CRICOS No. 00213J a university for the worldreal R Example: Element uniqueness • Consider the following algorithm: 17 CRICOS No. 00213J a university for the worldreal R Example: Element uniqueness • The worst case is when all elements are unique (or when only the last two elements are equal) – The basic operation is done once in the innermost loop body – The innermost loop occurs for j equal to i + 1 to n − 1, inclusive: – Outermost loop is performed for i equal to 0 to n − 2, inclusive: – Thus the algorithm’s worst-case efficiency is: 1 1 1 ( 1) ( 1) 1 1 n j i n i n i − = + = − − + + = − −∑ 2 2( 1) 1 1( ) ( ) 2 2 2worst n n C n n n O n − = = − ∈ 18 2 1 0 1 ( 1) ( 1 ) ( 1) ( 2) 1 2 n n i i n n n i n n i − − = = − − − = − + − + + = =∑ ∑ cai i=l u ∑ = c ai i=l u ∑ (ai ± bi ) i=l u ∑ = ai i=l u ∑ ± bi i=l u ∑ 1 i=l u ∑ = u − l +1, l ≤ u i i=1 n ∑ = n(n +1) 2 ≈ 1 2 n2 ik i=1 n ∑ ≈ 1 k +1 nk+1 CRICOS No. 00213J a university for the worldreal R Deriving efficiency classes from algorithm structure • With experience it is possible to identify an algorithm’s efficiency class from the pseudocode’s structure – Assignments v ← E are usually assumed to take constant time, i.e., to belong to class O(1) – The efficiency class of most compound statements can then be identified by inspection of the pseudocode – However, in tricky cases we may still need to produce summations or recurrence relations to determine the efficiency class accurately 19 CRICOS No. 00213J a university for the worldreal R Iterative code: Independent loops • For a loop that iterates a fixed number of times, the loop body is executed in direct proportion to the loop variable’s range for j ← 0 to n − 1 do x ← x + 1 // basic operation • Nested loops are analysed from the innermost to the outermost for i ← 0 to n − 1 do for j ← 0 to n − 1 do x ← x + 1 O(n) O(n) O(n2) 20 CRICOS No. 00213J a university for the worldreal R Sequential composition • For a sequence of statements S1, S2, …, Sk the total efficiency is the sum of the individual statements’ efficiencies • However, the overall order of growth is dominated by the largest polynomial term for any individual statement for i ← 0 to n − 1 do x ← x + 1 for i ← 0 to n − 1 do for j ← 0 to n − 1 do x ← x + 1 O(n) O(n2) O(n2) 21 CRICOS No. 00213J a university for the worldreal R Conditional statements • The worst-case order of growth for a conditional statement is the largest of any of its alternatives if B S1 else S2 O(m) O(n) O(max(m, n)) 22 CRICOS No. 00213J a university for the worldreal R Iterative code: Dependent loops • Where loop variables depend on one another we usually have to produce a summation to accurately identify the efficiency class for i ← 0 to n − 1 do for j ← i to n − 1 do x ← x + 1 because O(n − i) O(n 2) 23 1 1 2 2 0 0 1 ( 1) 1 1 (( 1) 1) ( ) ( 1) 1 ( ) 2 2 2 n n n i i i n n n i n i n n i n n O n − − = = = + − − + = − = + − + + = = = + ∈∑ ∑ ∑ cai i=l u ∑ = c ai i=l u ∑ (ai ± bi ) i=l u ∑ = ai i=l u ∑ ± bi i=l u ∑ 1 i=l u ∑ = u − l +1, l ≤ u i i=1 n ∑ = n(n +1) 2 ≈ 1 2 n2 ik i=1 n ∑ ≈ 1 k +1 nk+1 CRICOS No. 00213J a university for the worldreal R Iterative code: Uneven steps • Loops where the size of the steps decreases (or increases) by a power have a logarithmic (or exponential) growth i ← 1 while i < n do for j ← 0 to n − 1 do x ← x + 1 i ← i ∗ 2 because the inner loop’s body is always performed n times and when n equals 2k the outer loop’s body is performed k = log2 n times with i equal to 1, 2, 4, 8, 16, …, 2k−1 (or, equivalently, 20, 21, 22, 23, 24, …, 2k−1) O(1) O(n) O(n) O(n log n) 2 1 log ( log ) k x n n k n n O n n = = ⋅ = ⋅ ∈∑ 24 CRICOS No. 00213J a university for the worldreal R Iterative code: Balanced loops • In some situations two nested loops will counterbalance one another to produce an ‘obvious’ result in a non-obvious way i ← 1 while i < n do for j ← 1 to i do x ← x + 1 i ← i ∗ 2 because if n equals 2k then the inner loop is performed k = log2 n times with i equal to 1, 2, 4, 8, 16, …, 2k−1 and the basic operation is performed 20 + 21 + 22 + 23 + 24 + … + 2k−1 times in total O(i) O(1) O(i) O(n) ( ) 1 1 1 0 2 2 1 2 1 1 ( ) k kx k x n O n − − + = = − = − = − ∈∑ 25 cai i=l u ∑ = c ai i=l u ∑ (ai ± bi ) i=l u ∑ = ai i=l u ∑ ± bi i=l u ∑ 1 i=l u ∑ = u − l +1, l ≤ u i i=1 n ∑ = n(n +1) 2 ≈ 1 2 n2 ik i=1 n ∑ ≈ 1 k +1 nk+1 CAB301 Algorithms and Complexity��Lecture 2: Analysis of Algorithms Aims of this lecture References Analysis of algorithms Procedure of theoretical analysis of the efficiency of an algorithm Size of input Basic operation Example: Maximum and minimum values Example: Maximum and minimum values Example: Maximum and minimum values Some frequently-used�summation manipulation rules Big-O notation Big-O notation Big-O notation Example: Maximum and minimum values From efficiency function to big-O notation Example: Element uniqueness Example: Element uniqueness Deriving efficiency classes�from algorithm structure Iterative code: Independent loops Sequential composition Conditional statements Iterative code: Dependent loops Iterative code: Uneven steps Iterative code: Balanced loops