Term
| What are the main differences between Array and LinkedList |
|
Definition
*It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
*It's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.
*Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
*As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration. |
|
|
Term
| Merge Sort - algorithm and efficiency |
|
Definition
First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
Worst case performance O(n log n) |
|
|
Term
|
Definition
O(1)
ex. Determining if an integer (represented in binary) is even or odd |
|
|
Term
|
Definition
O(log n)
ex. Binary search
http://en.wikipedia.org/wiki/Binary_search |
|
|
Term
|
Definition
O(n)
ex. Finding the smallest item in an unsorted array |
|
|
Term
|
Definition
O(n log n)
ex. Fastest possible comparison sort
http://en.wikipedia.org/wiki/Comparison_sort |
|
|
Term
|
Definition
O(n^2)
ex. Bubble sort; Insertion sort |
|
|
Term
|
Definition
2^O(n)
ex.Solving the traveling salesman problem using dynamic programming |
|
|
Term
|
Definition
O(n!)
ex. Solving the traveling salesman problem via brute-force search. Or any brute-force algorithm. |
|
|
Term
| Traveling salesman problem |
|
Definition
Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city. NP-Hard
http://en.wikipedia.org/wiki/Traveling_salesman_problem |
|
|
