Asymptotic Notation (O, Ω, ) Describes the behavior of the time or space complexity for large instance characteristics
Common asymptotic functions
1 (constant), log n, n (linear)
n log n, n2 , n3
2n ( exponential), n!
where n usually refer to the number of instance of data (data的個數)
Common asymptotic functions
Common asymptotic functions
Other types of complexity: programming complexity, debugging complexity, complexity of comprehension.
Common asymptotic functions
Common asymptotic functions
Big-O notation The big O notation provides an upper bound for the function f
Definition:
f(n) = O(g(n)) iff positive constants c and n0 exist such that f(n) c g(n) for all n, nn0
e.g. f(n) = 10n2 + 4n + 2
then, f(n) = O(n2), or O(n3), O(n4), …
Ω(Omega) notation The Ω notation provides a lower bound for the function f
Definition:
f(n) = Ω(g(n)) iff positive constants c and n0 exist such that f(n) c g(n) for all n, nn0
e.g. f(n) = 10n2 + 4n + 2
then, f(n) = Ω(n2), or Ω(n), Ω(1)
notation The notation is used when the function f can be bounded both from above and below by the same function g
Definition:
f(n) = (g(n)) iff positive constants c1and c2, and an n0 exist such that c1g(n) f(n) c2g(n) for all n, nn0
e.g. f(n) = 10n2 + 4n + 2
then, f(n) = Ω(n2), and f(n)=O(n2), therefore, f(n)= (n2)
Sort Methods Insertion Sort
Bubble Sort
Selection Sort
Rank Sort
Shell Sort
Heap Sort
Merge Sort
Quick Sort
First 5 are simple (conceptually and to program). First 4 done in chapters 2 and 3. Shaker sort and shell sort are in the enrichment section of the text’s Web site. The remaining three are done in the algorithm design chapters of the text.
Insert An Element Given a sorted list/sequence, insert a new element
Given 3, 6, 9, 14
Insert 5
Result 3, 5, 6, 9, 14
Insert an Element 3, 6, 9, 14 insert 5
Compare new element (5) and last one (14)
Shift 14 right to get 3, 6, 9, , 14
Shift 9 right to get 3, 6, , 9, 14
Shift 6 right to get 3, , 6, 9, 14
Insert 5 to get 3, 5, 6, 9, 14
Insert An Element // insert t into a[0:i-1]
int j;
for (j = i - 1; j >= 0 && t < a[j]; j--)
a[j + 1] = a[j];
a[j + 1] = t;
Insertion Sort Start with a sequence of size 1
Repeatedly insert remaining elements
Insertion Sort for (int i = 1; i < a.length; i++)
{// insert a[i] into a[0:i-1]
// code to insert comes here
}
Insertion Sort for (int i = 1; i < a.length; i++)
{// insert a[i] into a[0:i-1]
int t = a[i];
int j;
for (j = i - 1; j >= 0 && t < a[j]; j--)
a[j + 1] = a[j];
a[j + 1] = t;
}
Insertion Sort (C++)
Complexity Space/Memory
Time
Count a particular operation
Count number of steps
Asymptotic complexity
Other types of complexity: programming complexity, debugging complexity, complexity of comprehension.
Comparison Count for (int i = 1; i < a.length; i++)
{// insert a[i] into a[0:i-1]
int t = a[i];
int j;
for (j = i - 1; j >= 0 && t < a[j]; j--)
a[j + 1] = a[j];
a[j + 1] = t;
}
Comments