|
|
Data Structure & Agorithms in Java
Table of Contents
 Time Complexity Analysis: Order
Linked List, Stacks, and Queue
Sorts
Search
Trees
Hashing
Disjoint Set ADT
Availabe download examples
- HashSetLinear.java Build a linear probing hash table called
HashSetLinear that extend from
the Abstarct Set class. This class included an Iterator methods as define follows:
add contains remove find .
- BinaryTree.java implements the binary tree with
add remove find methods.
Time Complexity Analysis: Order
- Definition: g(n) = O(f(n)) if there exists some positive real constant c and some nonnegative integer N such tat for all n ≥ N
g(n) ≤ c x f(n)
- Say that g(n) is big O of f(n), or g(n) is smaller than some positive
constant time f(n).
- Examples:
- 1. n^2 + 5n ≤ 2n^2 ==> n^2 + 5n <- O(n^2)
- 2. 5n^2 <- O(n^2). Because, for n >= 0, choose c = 5, N = 0.
==> 5n^2 = 5n^2.
- Definition: g(n) = o(f(n)) if there exists some positive real constant c and some nonnegative integer N such that, for all n ≥ N
g(n) ≤ c x f(n)
- Say that g(n) is little o of f(n), or g(n) is strictly less than some real constant c time f(n).
- lim g(n)/f(n) = 0 as n → ∞
- Example:
n <- o(n^2). Choose c > 0 implied that n ≤ cn^2
- Definition: g(n) = Ω(f(n)) if there exists some positive real constant c and some nonnegative integer N such that for all n ≥ N,
g(n) ≥ c x Ω(f(n))
- Say that g(n) is omega of f(n), or g(n) is greater than f(n) for some positive constant c.
- lim g(n)/f(n) = ∞ as n → ∞
- Examples
- 5n^2 <- Ω(n^2). Choose c=1 and N=0. n ≥ 0,
5n^2 ≥ 1 x n^2
- n^3 <- Ω(n^2).
- Definition: g(n) = Θ(f(n)), if there exits some real positive constant c and d some positive integer N such that for all n ≥ N
c x f(n) ≤ g(n) ≤ d x f(n)
- Say that g(n) is order of f(n), or g(n) is the curve lie between c x f(n) and d x f(n), where c
< d.
- Also, Θ(f(n)) = O(f(n)) ∩ Ω(f(n))
- lim g(n)/f(n) = c as n → ∞
- Example:
T(n) = n(n-1)/2 is in both O(n^2) and Ω(n^2); therefore, T(n) <-Θ(n^2)
- Examples
1. Running time of a for foop is O(n):
for(int i = 0; i <= n; i++)
A[i] = i;
2. ExchangeSort algorithm
void exchangeSort(int n, int A[]){
int i, j;
int temp;
for(i = 1; i <= n - 1; i++)
for(j = i+1; j <= n; j++)
if(A[j] < A[i]){
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
}
- Average case: T(n) = n^2/4 --> O(n^2)
- Worse case: T(n) = n(n-1)/2 --> O(n^2)
- Top Page
|
