Transcript Intro/Complexity Power Point Slides

COM212 Data Structures
• Intro to Abstract Data Structures
• 4 Weeks
• ~7 Homework Problems
• Implementation of Abstract Data Structures
• 7 Weeks
• ~7 Programming Assignments
• Test
• Advanced Java Programming
• 3 Weeks
• Project
Today
•
•
•
•
Complexity
Abstract Data Structures
Lists
Recursion
Complexity
• How long functions take to run
– Can be counted in number of instructions
executed
• Growth rate of functions
– How much longer they take to run as size of the
input increases
Example Function One
example(n)
print x
print y
x = y2
What is the run time?
Example Function One
example(n)
print x
print y
x = y2
The run time is 3.
Example Function Two
example(n)
loop n times
y=x+1
x = y2
print x
What is the run time?
Example Function Two
example(n)
loop n times
y=x+1
x = y2
print x
The run time is 4n
Example Function Three
example(n)
print x
print y
loop n times
y=x+1
x = y2
print x
What is the run time?
Example Function Three
example(n)
print x
print y
loop n times
y=x+1
x = y2
print x
The run time is 4n + 2
Complexity Notation
• We need some notation to help us categorize
functions by how long they take to run.
• Since the second two example functions will take
about the same time to run, they should be in the
same category.
• Even functions with run times of 2n and 3n take
similar time to run.
– They are much more dependent on n than a function
that takes constant time to run.
Example
A large n affects ex1() but not ex2()
ex1(n)
loop n times
print x
ex2(n)
print x
Big O
f(n) ≤ cg(n) for all n ≥ n0
Example
f(n) = 4n + 2
using g(n) = n and c = 5 and n0 = 2
f(n) ≤ cg(n) for all n ≥ n0
is
4n + 2 ≤ 5n when n ≥ 2
So g(n) is n. The complexity of f(n) is O(n)
Other Examples
O(n)
4n+8
¼(n-8)
200n+56801
O(n2)
4n2+18
O(1)
16
296
1000302
Others
56n + 7
0.34n – 455
0.003n2 + 3
14
5(lg n) + 5
98n4 + 2
Data Structures
• Data Types
• A way of representing or organizing data
• Examples
•
•
•
•
integer
float
character
array
5
6.543
a
Array
5
9
34
3
10
• Contiguous section of memory
• Fixed size
• Containing all one data type
6
Abstract Data Structures
• Independent of implementation
• User does not care about the implementation
• Set of operations to access / manipulate data
• Examples:
• FIFO queue
• Return the largest from a set
• List
Abstract Data Structure
• The user has a need for a specific DS, but
the actual implementation is not of their
concern.
• The actual implementation is hidden from
the user.
• The programmer needs to ensure that the
means of implementation allows the user to
do everything that is required.
Lists
List L = x0 x1 x2 x3 … xn-1 n = # elements
If a list is ordered than the key of xi-1 <= the key of xi for all i where 0 < i < n.
The sort symbol <= can be replaced by >= or any other function that determines
ordering in the keys.
An unordered list does not have this restriction.
Functions:
access(L, i)
length(L)
concat(L1, L2)
createEmptyList()
isEmptyList(L)
searchFor(L, key)
remove(L, i)
inserti(L, i, x)
insert(L, x)
sort(L)
returns xi
returns n
returns a new list with L2 concatenated on to L1
returns a newly created empty list
returns true if L is empty and false if it is not
returns i where key of xi = key
returns a list with xi removed; the old xi+1 is now xi, etc.
returns a list with x inserted as xi; the old xi is now xi+1, etc.
returns a list with x added to L
returns the list in sorted order
A Node
NameLast: Smart
FirstName: Joe
StudentNumber: 8
SSN: 123-34-1112
Grade: 95
Problem
• We need a list that has a maximum of 100
nodes.
• How can you implement this kind of list?
Homework 0
• Describe how to use an array to implement an
unordered list (assume a max size of 100
elements).
• Determine how to do the following functions:
access, length, concat, createEmptyList,
isEmptyList, searchFor, remove, and insert.
• How would any of these functions change if the
list was to be ordered?
Recursion