Scribd
Upload
16 views

Algorithms

Uploaded by

Dinh Nam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views

Algorithms

Uploaded by

Dinh Nam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Algorithm performance measurement

Methods:
1. Experiment: Implement in a computer and run it and record the time
Problems:
 Expensive
 Depend in the machine
 Trying variety of input is very cumbursume
2. Time complexity:
 Asymptotic complexity
 Polynomial complexity
Complexity methods: impact of input size variationon performance
1.Asymptotic: focus on the most dominating factor of the performance equation
a. Big-O: upper bound
P(n) = O(g(n))
If P(n) <= c.g(n)
For some c for all n >= no
P(n) = 10n2+5n+5 = O(n2) <= 16n2 for n >= no
P(n) >= 10n2 (Omega)
11n^2 >= P(n) >= 10n^2 (Theta)
0 < log n < n < n. log n < n^2 < n^3

Sorting Algorithm
a. Selection
b. Bubble
c. Insertion (Complexity = O(n^2))
void insertionSort(int arr[], int size)
{
int i,j;
int next;
for(i=1; i<size; i++)
{
next = arr[i];
for(j=i-1; j>=0 && next<arr[j]; j--)
arr[j+1]=arr[j];
arr[j+1] = next;
}
}
d. Merge sort
void merge(int array[], int const left, int const mid,
int const right)
{
int const subArrayOne = mid - left + 1;
int const subArrayTwo = right - mid;

// Create temp arrays


int *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temp arrays leftArray[] and rightArray[]


for (int i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (int j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

int indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;


int indexOfMergedArray = left;
// Merge the temp arrays back into array[left..right]
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}

// Copy the remaining elements of


// left[], if there are any
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
// Copy the remaining elements of
// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;

int mid = begin + (end - begin) / 2;


mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

e. Quick sort
f. Counting sort, bucket sort (linear time, does not compare elements)
g.Heap
+ e), f), g) are useful in most case
+ d), e), f) are not memory efficient, e) on an average quick: O(nlog n)
h. Lower bound on comparition based sorting algorithm (nlog n)

Devide & Conquer: Algorithm design technique


Steps :
1) Divide large problem into smaller sub problems
2) Combine the solutions to get solution to larger problem

Merge Sort
Divide the large problem into 2 smaller parts keep going until the smaller path
become 1 data point
Time to solve problem size n: T(n) = T(i) + T(j) + Solution Combining cost
T(n) = 2T(n/2) + n – 1
~ 2T(n/2) + n
= 2[ 2T(n/4) + n/2 ] +n
= 2^2 T(n/4) + 2n
= 2^k T(n/2^k) + kn
= nT(1) + n logn
Time complexity : O( nlogn)
Space complexity: O(n)
NOT POPULAR

Quick Sort
T(n) = T(i-1) + T(n-i) + n-1
No extra space required
T(1) = 0
Best case : when even split happens: T(n) = T(n/2) + T(n/2-1) + n-1
<= T(n/2) + T(n/2) + n = O(nlogn)
Worst case: when compare with the pivot element, all elements are on 1 side
T(n) = T(n-1) + n-1 = O(n^2)
Average case (Best and worst case happen alternately):
Tb(n) = 2Tw(n/2) + n – 1 = 2Tb(n/2 – 1) + 2(n-1) – 1 = 2Tb(n/2 ) + 2n
= O(nlogn)
Tw(n) = Tb(n-1) +n – 1 = 2Tw(n/2) + 2n
Examples:
T(n) = 3T(n/4) + nlogn

You might also like