What is a good Algorithm? (Cite from: Brian C. Dean )
- Always terminates and produces correct output.
- Make efficient use of computational resources.
Minimizes running time, memory usage, processors, bandwidth, power consumed, heat produced. - Is simple to describe, understand, analyze, implement, and debug
For example:
Linear search:
1 |
for (int i = 0; i<N; i++) { |
Binary search:
1 |
low = 0; high = N-1; |
Linear search: O(N) time.
Binary search: O(log N) time.
Running time
What is the Linear search: O(N) time.
meaning in the above? We usually use asymptotic notation
to describe how running time scales with input size.
O(f(N)) means “upper-bounded by a constant times f(N) as N grows large”. Just like, if the input of size is N, then the take about nN machine instructions, then we can say it runs in O(N) time.
There are other two symbol which are used for discribe the running time scales with input size.
- Ω() provides an asymptotic lower bound.
- Θ() means both a lower and upper bound.
Arrays, Listed lists
Arrays
After you define the size of the arrays, you can change the size of the array at the running time. You just can allocate for a new arrays at the running time and copy the old one to the new one.
1 |
|
Analyze:
- Retrieve or modify any element in O(1) time.
- Insert or delete in middle of list: O(N) time.
- Insert or delete from ends: O(1) time
Linked Lists
1 |
/* In C, typically |
TODO:
- [ ] Task1:Write the doubly linked lists.
- [ ] Write a list which maintain a pointer to the first and last element.
Analyze:
- Seek to any position in list: O(N) time.
- Then insert or delete element: O(1) time.
- Insert or delete from ends: O(1) time.
Circular Arrays, Queues
1 |
void enqueue(int x) |
Stacks
1 |
void push(int x) |
Arrays Vs Lists Example
We can use a example(From Brian. Dean) to introduce the running time abou the Arrays and Lists.
In the file studens.txt
have a lot of students information about their name. Like this follow:
1 |
Sebastian Valentin |
Question:
Write for me a program in C++ that takes as input a list of names, and prints out each name that appears in the list multiple times.
Arrays Solution:
1 |
|
List Solution
1 |
|
近期评论