1 O(1)
1.1 O(1): array access
class Test {
int a[100];
public:
int get( int n ) {
return a[n];
}
void set( int n, int value ) {
a[n]=value;
}
}
1.2 O(1): list
class Test {
std::list<int> alist;
void append( int value ) {
alist.push_back( value );
}
void getFirst() {
return alist.front();
}
};
1.3 O(1): stack
void test() {
std::stack<int> mystack;
mystack.push(100)
int a = mystack.pop()
}
2 O(n)
2.1 O(n): sum up an array
#define N 100
int a[N];
int sum_array() {
int total=0;
for( int i=0;i<N;i++) {
total += a[i]
}
return total;
}
2.2 O(n): sum up a list
typedef struct _lnode_ {
struct _lnode_ *next;
int value;
} lnode;
lnode list;
int sum_list() {
int total=0;
for( lnode=&list; lnode!=NULL; lnode=lnode->next ) {
total += lnode->value
}
return total;
}
3 O(log n)
3.1 O(log n): search in a sorted array
#include <stdio.h>
#define N 10
int a[N]={ 1,2,3,4,5,6,7,8,9, 10};
/*
return -1: not found
*/
int find( int v ) {
int s=0;
int e=N-1;
int mid;
/*
if( (v>a[N-1] ) || (v<a[0])) {
return -1;
}*/
while( e>=s ) {
mid=(s+e)/2;
if( a[mid]==v )
return mid;
if( a[mid] > v ) {
e = mid-1;
} else {
s = mid+1;
}
}
if( a[s]==v )
return s;
if( a[e]==v )
return e;
else
return -1;
}
int main() {
int i ;
i = find(10);
printf("i=%d\n",i);
return 0;
}
3.2 Finding largest/smallest number in a binary search tree
#include<stdio.h>
#include<stdlib.h>
#include <memory.h>
#include <time.h>
/*
binary-tree-search.c
gcc binary-tree-search.c
*/
typedef struct _tnode_
{
int value;
struct _tnode_ *left, *right;
}tnode_t;
// A utility function to create a new BST _tnode_
tnode_t *new_node(int value)
{
tnode_t *temp = (tnode_t *) malloc( sizeof(tnode_t));
temp->value = value;
temp->left = temp->right = NULL;
return temp;
}
void delete_tree(tnode_t* root) {
tnode_t* node;
if( root==NULL) return;
if( root->left != NULL ) {
delete_tree( root->left );
root->left = NULL;
}
if( root->right != NULL ) {
delete_tree( root->right );
root->right = NULL;
}
if( ( root->left == NULL ) && (root->right==NULL) )
free(root);
}
tnode_t * insert(tnode_t* root, int value)
{
if ( root == NULL) return NULL;
tnode_t * node=root;
while( node !=NULL ) {
if( node->value == value )
return node;
else if( node->value > value ) {
if( node->right!=NULL ) {
node = node->right;
} else {
node->right = new_node( value );
return node->right;
}
} else {
if( node->left!=NULL) {
node = node->left;
} else {
node->left = new_node( value );
return node->left;
}
}
}
/*never reach here*/
return node;
}
tnode_t * find( tnode_t * root, int value ) {
if ( root == NULL) return NULL;
tnode_t * node=root;
while( node !=NULL ) {
if( node->value == value )
return node;
else if( node->value > value ) {
node = node->right;
} else {
node = node->left;
}
}
return node;
}
#define N 10
int main()
{
int i,v;
int a[N];
int max=-1;
tnode_t *root=NULL, *node;
srand(time(0));
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
if( max<a[i] ) {
max=a[i];
}
}
printf("\nmax=%d\n",max);
root=new_node(a[0]);
for( int i=1;i<N;i++) {
insert( root, a[i] );
}
node = find( root, max );
if( node!=NULL ) {
printf("node=%p, value=%d\n", node, node->value );
}
delete_tree(root);
return 0;
}
4 O(n log n)
4.1 Merge Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bottom_up_merge( int in[], int left, int right, int end, int out[]);
#define min( a, b ) ( (a)>(b)?(b):(a) )
// array A[] has the items to sort; array B[] is a work array
void bottom_up_merge_sort(int A[], int n)
{
int B[n];
int width,i,e=0;
int *pa=A, *pb=B, *p;
// Each 1-element run in A is already "sorted".
// Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted.
for (width = 1; width < n; width = 2 * width)
{ e++;
// Array A is full of runs of length width.
for (i = 0; i < n; i = i + 2 * width)
{
// Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
// or copy A[i:n-1] to B[] ( if(i+width >= n) )
bottom_up_merge(pa, i, min(i+width, n), min(i+2*width, n), pb);
}
p = pa;
pa=pb;
pb = p;
// Now array A is full of runs of length 2*width.
}
if( e%2==1 ) {
for( i=0;i<n;i++ ) {
A[i]=B[i];
}
}
}
/*
0,1,...,left,...,left+width-1,right=left+width,...,left+2*width-1, end=left+2*width,...,n-1
in [ ]
out[ ]
merge two data blocks: in[left, ..., right-1], in[right,....,end-1]
the result is out[left,..., end-1]
*/
void bottom_up_merge( int in[], int left, int right, int end, int out[])
{
int L,R,i;
L = left, R = right;
// While there are elements in the left or right runs...
for (i = left; i < end; i++) {
// If left run head exists and is <= existing right run head.
if (L < right && (R >= end || in[L] <= in[R])) {
out[i] = in[L];
L = L + 1;
} else {
out[i] = in[R];
R = R + 1;
}
}
}
#define N 10
int main()
{
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
bottom_up_merge_sort(a, N);
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
Worst Case Time Complexity [ Big-O ]: O(n*log n)
Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: O(n*log n)
Space Complexity: O(n)
4.2 Heap Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*for each tree node, sub-tree node, the root is larger than any child*/
void heapify( int arr[]/*the heap array*/,
int n/*length of the array*/,
int p/*index of the parent node*/)
{
// Find maxi among root, left child and right child
int maxi = p;
int l = 2*p + 1;
int r = 2*p + 2;
int temp;
if (l < n && arr[l] > arr[maxi])
maxi = l;
if (r < n && arr[r] > arr[maxi])
maxi = r;
// Swap and continue heapifying if root is not maxi
if (maxi != p)
{
temp = arr[p];
arr[p]=arr[maxi];
arr[maxi] = temp;
heapify(arr, n, maxi);
}
}
// main function to do heap sort
void heap_sort( int arr[]/*the array to sort*/,
int n /*the length of the array*/)
{ int temp;
// Build max heap
/*heapify all the sub-trees, from bottom up */
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
/*each time, reduce the length of the heap*/
for (int i=n-1; i>=0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
#define N 10
int main() {
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
heap_sort(a, N);
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
Worst case time: O(nlgn)
Best case time: O(n)
Average case time: O(nlgn)
Space: O(1)
4.3 Quick Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quick_sort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quick_sort(arr, left, j);
if (i < right)
quick_sort(arr, i, right);
}
#define N 10
int main() {
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
quick_sort( a, 0, N-1 );
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
Best Time Complexity : Ω(n log(n))
Average Time Complexity : Θ(n log(n))
Worst Time Complexity : O(n^2)
Space Complexity: O(log(n))
5 O(n^2)
5.1 Bubble Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bubble_sort( int a[], int length ) {
int i,j, temp;
for( i=0;i< length-1;i++) {
for( j=i+1;j<length;j++) {
if( a[i]>a[j] ) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
#define N 10
int main() {
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
bubble_sort( a, N);
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
i max times of swap
--------------------------
1: n-1
2: n-2
3: n-3
. .
. .
. .
n-2: 2
n-1: 1
--------------------------
1+2+3+...+(n-1) = n(n-1)/2 => O(n^2)
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)
5.2 Insertion Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void insertion_sort(int ar[], int length )
{
int i,j, n;
for ( i=1; i < length; i++) {
/*a[0],...,a[i-1] are sorted, we want to insert a[i] into the sorted queue*/
n = ar[i]; j = i;
while (j > 0 && ar[j-1] > n ) {
/*move the sorted elements to make room for the new elemment */
ar[j] = ar[j-1];
j--;
}
/*insert the new element to the sorted part*/
ar[j] = n;
}
}
#define N 10
int main()
{
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
insertion_sort(a, N);
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
insertion_sort()
i max times of swap
--------------------------
1: 1
2: 2
3: 3
. .
. .
. .
n-2: n-2
n-1: n-1
--------------------------
1+2+3+...+(n-1) = n(n-1)/2 => O(n^2)
Worst Case Time Complexity [ Big-O ]: O(n^2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n^2)
Space Complexity: O(1)
5.3 Selection Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selection_sort(int ar[], int length ){
int i,j;
int min, temp;
for(i = 0; i< length; i++)
{
min = i;
for (j = i+1; j < length; j++)
if (ar[j] < ar[min]) min = j;
temp = ar[i];
ar[i] = ar[min];
ar[min] = temp;
}
}
#define N 10
int main()
{
int a[N];
srand(time(0));
printf("\n");
for( int i=0;i<N;i++) {
a[i]=rand()%100;
printf("%d\t",a[i]);
}
printf("\n");
selection_sort(a, N);
for( int i=0;i<N;i++) {
printf("%d\t",a[i]);
}
printf("\n");
return 0;
}
selection_sort()
i max times of swap
--------------------------
1: 1
2: 2
3: 3
. .
. .
. .
n-2: n-2
n-1: n-1
--------------------------
1+2+3+...+(n-1) = n(n-1)/2 => O(n^2)
Worst Case Time Complexity [ Big-O ]: O(n^2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n^2)
Space Complexity: O(1)
6 O(2^n)
6.1 Fibonacci Sequence
int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}