31251 Lecture Notes - Lecture 3: Big O Notation
30 Jun 2018
School
Department
Course
Professor
the vector class
• Arrays in C/C++ are difficult.
• Lists provide an alternative to this, but
• Lists usually don’t have guarantees about how the memory is managed.
• Lists also often come with more overhead.
• If you don’t care what’s inside, you can think of vectors as dynamically size arrays.
Templates
• Templates provide a way to write certain types of code once:
• If the code doesn’t care about the types it’s working with.
• So we can easily make vectors that hold different types without rewriting the code.
• They’re fairly simple to work with, but provide lots of places to leave something out (and
cause weird compile errors).
Iterators
• Iterators in Java are fairly well put together.
• In particular, the inheritance structure is well thought out. A little wordy, but
simple.
• As you might expect, in C++ they’re a lot more flexible, but you pay for this with some ugly
code.
• Also, the inheritance structures are not as well defined, so using them is a little more
cumbersome.
Analysing and Comparing Algorithms: Big Oh Notation
• How do we reliably compare algorithms?
• Testing gives good information but is limited to the cases you test.
• How much of that information comes from the choice of computer, programming
languages, test data?
• We need a way of comparing the abstract algorithms themselves.
Algorithm Analysis
• If we have two algorithms that solve the same problem, what things are we interested in?
• How long they take.
• How much space they take up.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
