程序代写代做 algorithm graph C data structure Complexity and Data Structures

Complexity and Data Structures
Daniel Archambault
CS-115: Complexity
1

Previously in CS-115
a
Graphs connect the world!
CS-115: Complexity
2

Previously in CS-115
What differentiates a graph from a tree?
CS-115: Complexity
3

Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
CS-115: Complexity
3

Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
CS-115: Complexity
3

Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
CS-115: Complexity
3

Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
What are two graph data structures that implement the ADT?
CS-115: Complexity
3

Previously in CS-115
What differentiates a graph from a tree? What is a directed graph?
What is an undirected graph?
What is degree?
What are two graph data structures that implement the ADT? What are advantages/disadvantages?
CS-115: Complexity
3

Previously in CS-115
Complexity of algorithms? What about data structures?
Complexity and Data Structures
CS-115: Complexity
4

Complexity, Data Structures, and Sorting
Complexity tries to quantify how fast or big something is
􏰀 given an input size of n how long could this take?
􏰀 given an input size of n how much memory/space do we need?
We use n as the input size because it’s variable
With big n, sometimes a lot of time and space is required!
In this lecture, we look at worst case (how bad it can get) and average case complexity.
CS-115: Complexity
5

Rules of Complexity
In complexity, we worry only about the largest exponent We ignore all constant values and lower exponents
􏰀 2n3 +32n2 +4 is O(n3)
Why can we do this? As n becomes really large, other terms don’t matter so much.
CS-115: Complexity
6

Space Complexity
You have already done time complexity? Think sorting…
Well, you can use the same tool to talk about how much space something takes in memory.
􏰀 Given an input size of n, it’s possible for it to take O(n2) space Important for data structures
􏰀 time complexity for the operations on the data
􏰀 space complexity for the data itself
CS-115: Complexity
7

Warning!
In this lecture we estimate complexity
We are providing estimates not proofs Complexity theory is hard and involves proofs
􏰀 particular algorithm has performance…
􏰀 any algorithm for a problem will have performance…
Our arguments are not proofs, but estimates In second year, you will do rigourous proofs.
CS-115: Complexity
8

Array Complexity
int[] a = new int [n];
Insertion complexity?
CS-115: Complexity
9

Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity?
CS-115: Complexity
9

Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity? O(1) Space complexity?
CS-115: Complexity
9

Array Complexity
int[] a = new int [n];
Insertion complexity? O(n) Access complexity? O(1)
Space complexity? O(n)… usually
CS-115: Complexity
9

Linked List Complexity
head
next element
Obj.
tail
next next null element element
Obj. Obj.
Insertion complexity (if location known)?
CS-115: Complexity
10

Linked List Complexity
head
next next element element
tail
next null element
Obj. Obj. Obj.
Insertion complexity (if location known)? O(1) Access complexity?
CS-115: Complexity
10

Linked List Complexity
tail
next element
next element
next element
head
Obj.
Insertion complexity (if location known)? O(1) Access complexity? O(n)
Space complexity?
null
Obj.
Obj.
CS-115: Complexity
10

Linked List Complexity
tail
next element
next element
next element
head
Obj.
Insertion complexity (if location known)? O(1) Access complexity? O(n)
Space complexity? O(n)
null
Obj.
Obj.
CS-115: Complexity
10

Queue
dbef
c
isEmpty complexity?
CS-115: Complexity
11

Queue
dbef
c
isEmpty complexity? O(1) enqueue/dequeue complexity?
CS-115: Complexity
11

Queue
dbef
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity?
CS-115: Complexity
11

Queue
d
b
e
f
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity? O(1)
Space complexity?
CS-115: Complexity
11

Queue
d
b
e
f
c
isEmpty complexity? O(1) enqueue/dequeue complexity? O(1) peek complexity? O(1)
Space complexity? O(n)
CS-115: Complexity
11

Stack
12 51 17
isEmpty complexity?
CS-115: Complexity
12

Stack
12 51 17
isEmpty complexity? O(1) push/pop complexity?
CS-115: Complexity
12

Stack
12 51 17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity?
CS-115: Complexity
12

Stack
12
51
17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity? O(1) Space complexity?
CS-115: Complexity
12

Stack
12
51
17
isEmpty complexity? O(1) push/pop complexity? O(1) peek complexity? O(1) Space complexity? O(n)
CS-115: Complexity
12

Binary Search Tree
Find a element?
CS-115: Complexity
13

Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
􏰀 a balanced binary tree has maximum height of O(lg(n))
􏰀 O(lg(n)) – log base 2 of n
Print out in alphabetical order?
CS-115: Complexity
13

Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
􏰀 a balanced binary tree has maximum height of O(lg(n))
􏰀 O(lg(n)) – log base 2 of n
Print out in alphabetical order? O(n) Space complexity?
CS-115: Complexity
13

Binary Search Tree
Find a element? can be O(n) but usually O(lg(n))
􏰀 a balanced binary tree has maximum height of O(lg(n))
􏰀 O(lg(n)) – log base 2 of n
Print out in alphabetical order? O(n) Space complexity? O(n)
CS-115: Complexity
13

Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2 3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element?
CS-115: Complexity
14

Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2 3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element?
CS-115: Complexity
14

Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2
3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element? assume good hash function O(1) Space complexity?
CS-115: Complexity
14

Hash Maps
Hash Function
”Dan!”
”Swansea!” ”Oh No!”
0
3 1
1 2
3
3
4
(”Swansea!”, 33)
(”Dan!, 27)
(”Oh No!”, 8)
Find a element? assume good hash function O(1) Insert an element? assume good hash function O(1) Space complexity? usually O(n)
CS-115: Complexity
14

Heaps and Priority Queues
27
27 8422
Look at the top?
10
CS-115: Complexity
15

Heaps and Priority Queues
27
27 8422
Look at the top? O(1) Insert an element?
10
CS-115: Complexity
15

Heaps and Priority Queues
27
27 8422
Look at the top? O(1) Insert an element? O(lg n) Remove the front/root?
10
CS-115: Complexity
15

Heaps and Priority Queues
27
27 8422
Look at the top? O(1)
Insert an element? O(lg n) Remove the front/root? O(lg n) Space complexity?
10
CS-115: Complexity
15

Heaps and Priority Queues
27
27 8422
Look at the top? O(1)
Insert an element? O(lg n) Remove the front/root? O(lg n) Space complexity? usually O(n)
10
CS-115: Complexity
15

Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)?
CS-115: Complexity
16

Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node?
CS-115: Complexity
16

Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node? O(n)
Space complexity?
CS-115: Complexity
16

Graphs: Matrix
Node[] nodes; //list of n nodes (made by
constructor)
Edge[][] matrix; //nxn matrix specified by
constructor
Look up or remove an edge (given its 2 nodes)? O(1) Look up or remove a node? O(n)
Space complexity? O(n2)
CS-115: Complexity
16

Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge?
CS-115: Complexity
17

Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node?
CS-115: Complexity
17

Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node? O(n) Space complexity?
CS-115: Complexity
17

Graphs: Linked
public class Graph {
Node[] nodes;
…. }
public class Node {
Edge[] edgeList; //list of degree nodes
}
Look up or remove an edge? O(n) Look up or remove an node? O(n) Space complexity? O(n + e)
CS-115: Complexity
17

Complexity of Comparison-Based Sorting
All sorting algorithms currently are comparison based
􏰀 general sorting algorithms that involves knowing nothing about data
We know that there are algorithms that take O(n lg n) comparisons But, surely, there are faster algorithms, Dan?
CS-115: Complexity
18

Complexity of Comparison-Based Sorting
All sorting algorithms currently are comparison based
􏰀 general sorting algorithms that involves knowing nothing about data
We know that there are algorithms that take O(n lg n) comparisons But, surely, there are faster algorithms, Dan?
For comparison-based sorts, no.
􏰀 mathematical proof says you need at least Ω(n lg n) comparisons
􏰀 proof is hard, but we can do it for fun sometime…
However, if you know something about the data, you can do better!
CS-115: Complexity
18

Bucket Sort: O(n)
If you know that your data can be easily divided into b buckets, you can use bucket sort which is O(n).
The algorithm:
􏰀 Create an array of b elements. Each stores an array or linked list.
􏰀 Traverse all n unsorted elements, throwing each into their correct
bucket.
􏰀 Assuming each bucket has a small number of elements, sort by any
means.
If any particular bucket ends up with n elements it is O(n2) Bucket sort is really useful, especially with hashmaps
􏰀 I’ve personally used this strategy many times.
CS-115: Complexity
19

Radix Sort: O(n)
If you know that each element of your data has a key of b digits, you can use radix sort which is O(bn).
Algorithm:
􏰀 start with the least significant digit and apply bucket sort
􏰀 loop through all digits up to the greatest digit
Assumption is good bucket sorts and small number lengths. What to do with non-integer keys…
Still much debate about its complexity
CS-115: Complexity
20