Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Algoritma dan Struktur Data : Analisis Algoritma

Time & Space

Why do we need computers ? 

Problems :

• How long will my program take ? (time) 
• Why does my program run out of memory ? (space) 

The Factors :

Algorithms Analysis

Better algorithm = algorithm with the shortest running time 

Two approaches : 

• Experimental Approach 
• Asymptotic Analysis

Experimental Approach

Experimental Approach: Disadvantages

Disadvantages :

• Inputs: 
• Good sample ? 
• H/W limitation to test inputs 
• Applied to all instances ? 
• H/W and S/W environment ? 
• Implementation first ?

Mathematical Analysis

Analyzing the running time of algorithms : 

• All possible inputs 
• Evaluate relative efficiency of any algorithms 
• Independent from the software and hardware environment 
• Used before implementation

Mathematical Analysis: Tools

Algorithm can be studied on a language- and machine-independent way. 

Tools : 

• Pseudocode (Language-independent) 
• RAM model (Machine independent) 
• The Asymptotic Analysis 

RAM Model

Generic one-processor model. Define the instruction precisely. Contains instructions common computers : 

• arithmetic 
• data movement (load, store, copy) 
• control (conditional, looping, methods call, return, ...)
• Data type : integer and floating point 

Simple operations => exactly one-time step 

• arithmetic operation (=, +, x, -, square root, exponentiation, etc.) 
• comparing two numbers 
• indexing into an array 
• returning from a method 
• etc... 

Loops and subroutines != simple operations. Instructions are executed one after another, with no concurrent operations.

Analysis in RAM

Input Size:

The number of items in the input (ex.: the array size n for searching).

For many other problems, it might be different (ex:. graph is described by the number of vertices and edges).

The total running time of an algorithm: 

• The cost of executing each statement 
• The frequency of execution of each statement 

Assumption: 

• each execution of the i-th line takes time c_i 
• c_i is a constant

Example: Reversing an Array

Running Time :

T(n) = C_1 (1)+C_2 (n+1)+C_3 (n)+C_4 (n)+C_5 (1) 

T(n) = C_1+C_2+C_5+〖(C〗_2+C_3+C_4)n 

T(n) is a linear function of n.

Example: Matrix Transpose

T(n) = C_1 (n+1)+C_2 (n(n+1))+C_3 (n(n))+C_4 (1)

T(n) = C_1+〖C_4+(C〗_2+C_3)n^2+〖(C〗_1+C_2)n

T(n) is a quadratic function of n.

Example: Exponentiation of 2

The value of i changes x times from 2^0, 2^1, 2^2,…,2^((x-1))

2^((x-1))≤n, so x=log_2⁡n+1 

T(n)=C_1+(C_2+C_3+C_4 )x 

T(n)=C_1+(C_2+C_3+C_4 )(〖1+log〗_2⁡n) 

T(n) is logarithmic function of n. 

Example: Find

ComputeT(n), the running time of algorithm FIND:

Execution time depends on the location of X in the Array: 

• Worst case : T(n)=n 
• Best case : T(n)=1 
• Average case : ?? 

Best, Worst, and Average Case

For a particular problem, the figure below represents each input instance as a point.

Order of Growth

Time complexities: numerical functions over the size of possible problem instances. Very difficult to work precisely with those functions:

• It’s complicated function 
• RAM model = simplification of actual process in computer 

Efficient algorithm: its worst-case running time has a lower order of growth.

Asymptotic Notation

It proves to be much easier to talk in terms of simple upper and lower bounds of time-complexity functions using the Asymptotic notation.

The Asymptotic notation :

• Ignores: the difference between multiplicative constants factors (f(n)=2n and g(n)=n are identical). Why?
• Consider: only the leading term of a formula. Why? (e.g., n^3 from 7n^3+100n^2+275000)

Is it possible that algorithm with lower order of growth run slower than the other with higher order of growth?

f(n) = n^2+100n+log_10⁡n+1000

Upper Bound

f(n)=O(g(n)) means c.g(n) is an upper bound on f(n).

There exists some constant c such that f(n) is always ≤g(n), for large enough n (n≥n_0) for some constant n_0). 

Lower Bound

f(n)=Ω(g(n)) means c.g(n) is a lower bound on f(n). 

There exists some constant c such that f(n) is always ≥g(n), for all n≥n_0. 

Tight Bound

f(n)=Ɵ (g(n)) means c_1.g(n) is an upper bound on f(n) and c_2.g(n) is a lower bound on f(n), for all n≥n_0.

There exist constants c_1 and c_2 such that f(n)≤c_1.g(n) and f(n)≥c_2.g(n). 

It is called tight bound

Example

Growth Rate Classification

Listed in order of increasing running time for the same input size n:

• Constant => f(n)=1. 
• Running time does not depend on the input size n 
• Logarithmic => f(n)= log⁡n 
• The base of the logarithm is not relevant with respect to the order of growth (since all logarithms with a constant base are related by a constant factor). Example : Binary Search.

Listed in order of increasing running time for the same input size n:

• Linear =>  f(n)=n
• Measure the cost of looking at each item once in an n-element array. Example : finding the biggest item.
• Linearithmic / Superlinear / n-log-n => f(n)=n lg⁡n
• This important classification arises in such algorithms as Quicksort and Mergesort.
• Quadratic => f(n)=n^2
• Measure the cost of looking at most or all pairs of items in an n-element universe. Example : Insertion Sort
• Cubic =>  f(n)=n^3
• Enumerate through all triples of items in an n-element universe
• Exponential =>  f(n)=c^n for a given constant c>1
• Enumerate all subsets of n items
• Factorial =>  f(n)=n!
• Generating all permutations or orderings of n items.

Running Time Comparison

Importance

Two different computers:

• Computer A : execute 10 billion instructions per second
• Computer B : execute 10 million instructions per second

Sorting Algorithms

Two of them are :

1. Insertion Sort, worst-case running time is O(n^2). The best programmer codes this sort, number of instructions are 2n^2
2. Heap Sort, worst-case running time is O(n lg⁡〖n)〗. Mediocre programmer codes this sort, number of instructions are 50n log n

We want to sort n = 10 millions 8-byte integers (10 megabytes of data) 

Faster computer run the insertion sort program: 

〖〖(2(10〗^7)〗^2 instructions)/(10^10 )(instructions/seconds) = 20.000 seconds (5.6 hours) 

Slower computer run the merge sort program: 

(50(10^7 )lg10^7 insturctions)/(10^7 (instructions/second) ) = 1163 seconds (almost 20 minutes) 

Computer B runs 17 times faster than computer A !!

Exercises

Hitunglah kompleksitas dari 3 buah algoritma di bawah ini !

Describe an algorithm that given a list of n integers (sorted in increasing order) and an integer x, determines whether or not there exist two elements in S whose sum is exactly x. Compute the running time of your algorithm !

Sumber

Slide ASD : Analisis Algoritma

http://informatika.unpar.ac.id/