Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Concept Challenge: Estimating Big O from Code

Loading...

Data Structures and Performance

Université de Californie à San Diego

4.8 (1,670 évaluations) | 54K étudiants inscrits

Cours 4 de 4 dans Object Oriented Programming in Java Spécialisation

How do Java programs deal with vast quantities of data? Many of the data structures and algorithms that work with introductory toy examples break when applications process real, large data sets. Efficiency is critical, but how do we achieve it, and how do we even measure it? This is an intermediate Java course. We recommend this course to learners who have previous experience in software development or a background in computer science, and in particular, we recommend that you have taken the first course in this specialization (which also requires some previous experience with Java). In this course, you will use and analyze data structures that are used in industry-level applications, such as linked lists, trees, and hashtables. You will explain how these data structures make programs more efficient and flexible. You will apply asymptotic Big-O analysis to describe the performance of algorithms and evaluate which strategy to use for efficient data retrieval, addition of new data, deletion of elements, and/or memory usage. The program you will build throughout this course allows its user to manage, manipulate and reason about large sets of textual data. This is an intermediate Java course, and we will build on your prior knowledge. This course is designed around the same video series as in our first course in this specialization, including explanations of core content, learner videos, student and engineer testimonials, and support videos -- to better allow you to choose your own path through the course!

Visualiser le programme de cours

Compétences que vous apprendrez

Trees (Data Structures), Data Structure, Linked List, Binary Tree

Avis

4.8 (1,670 évaluations)

5 stars
1,390 ratings
4 stars
241 ratings
3 stars
31 ratings
2 stars
5 ratings
1 star
3 ratings

AE

Dec 06, 2016

Very solid review of data structures. In fact, I learned a lot of new things along the way like how to benchmark test Java code and how to properly use JUnit and other unit testing frameworks.

YK

Jan 11, 2016

I really liked this course and the way it was taught. Although I am a CS major, I really learnt a lot of other stuff from this course apart from learning the core content of Data Structures.

À partir de la leçon

Efficiency Analysis and Benchmarking

Welcome to week 3! The text-editor application you worked with last week does something, but it doesn't do it particularly fast. This week we'll start talking about efficiency. We'll introduce the concept of "Big-O" notation, which sounds a little silly, but is really a powerful (and extremely common) way of analyzing a program's efficiency, independent of the system that it's running on and the exact details of how it's implemented. Then we'll go the other direction and dive into the details, talking about how to measure the actual running time of a piece of code to get an idea of how it really performs in practice.

Core: Our Motivation for Asymptotic Analysis8:28

Core: Counting Operations9:57

Core: Introduction to Asymptotic Analysis, Part 19:11

Core: Introduction to Asymptotic Analysis, Part 23:48

Core: Computing Big O with Consecutive Operations5:19

Core: Computing Big O with Nested Operations5:22

Concept Challenge: Classifying Functions using Big O7:52

Support: Analyzing Selection Sort8:41

Concept Challenge: Estimating Big O from Code6:08

Core: Worst, Best, and Average Cases8:16

In the Real World: Worst Case Analysis1:30

Core: Analyzing Search Algorithms6:25

Core: Analyzing Sorting Algorithms9:25

When I struggled: Algorithm performance1:31

Core: Merge Sort11:07

Core: A Summary of Sorting4:00

Core: Common Pitfalls in Asymptotic Analysis5:51

Enseigné par

Christine Alvarado
Associate Teaching Professor
Mia Minnes
Assistant Teaching Professor
Leo Porter
Associate Teaching Professor

Transcription

In this concept challenge we're gonna look at a nested for loop, in fact a triply nested for loop, to try to figure out what the big-O running time of this code is. So same format as the other concept challenges. Work on it on your own. Discuss it and watch the UC San Diego's learners discuss. Try the problem again. And then, confirm your understanding with our explanation. So here's the problem. We've got this code that you can see here. It's a triply nested for loop, and the question is, in terms of n, what is the big-O running time, tightest bound, for this code? >> Hi, I'm Tina. >> Hi, my name is Gev. >> Hi, my name is Robert. >> So what I noticed with this code is, that we have three nested for loop lines, and so I would think that we could figure out the run time for each line, and then multiply those three together, and see what we get from there. >> Okay, well for the first outer loop, that starts at i=0 and goes all the way up to 2*n. So that's, I think, the run time for the first loop. And then, the second loop looks a little bit more confusing cuz if we start it at n- 1000, I'm a little bit confused about that. >> So, I think for the second one, since you're subtracting 1000, so all you have to do is increment the 1000, so that would just be 1000 counts for the run time. >> And for the last one, I noticed our first starting index has n in it, or in this case n over 2, but it looks like it's from n over 2 to n. So I'd think it'd be, overall the run time for that line would be n over 2, does that seem like it? >> Yeah, and you said we had to multiply them, all of them, to get the run time? >> Yeah. >> Yeah, that sounds right. >> So, I think that comes out to be 2*n, times 1000, times n over 2, and I think we can ignore the 1000, because it's a constant. So, that comes out to be n squared, I believe. >> Yeah, n squared. >> Right. >> All right, so the key to analyzing this triply nested for loop, as Mia showed you, is to analyze the number of instructions that are done in each body of the for loop from the inside out. Because the innermost for loop here is going to be executed to completion every time the next-outermost for loops runs once. Similarly, for this next outermost for loop, it will be run to completion every time this outermost for loop runs. So let's begin at the very inner layer, this instruction right here which is the body of the innermost for loop. And we need to count the number of instructions in that body. Well, of course there is just one instruction in that body, that sum++. So, the amount of time that that body takes is just order 1. So, now we can calculate how many times does this innermost for loop run its body, which just has one instruction in it. So, to do that, we need to look at the loop bounds and where the control variable starts, where it ends, and how much we add to it each time through. So, we have this control variable k. It starts at n over 2. It goes as long as k is less than n, and we add one to k each time through the loop. So, how many times is that going to execute? Well, it's going to execute all the way up from n over 2 to n, stepping along one each time, and that's gonna be n over 2 times. But n over 2 in big-O notation is really just order n, so this loop runs order n times, executing 1 each time in its body. And so the entire loop Is going to be order n. So, from start to finish, that entire inner loop is going to take order n steps. So now let's back out, and figure out how many times this next most inner loop runs. Again, we look at the loop header. We have j starting at n- 1000, going up to n, and we're adding one each time. Now, this one's a little bit tricky, because if we count the number of steps, even though there's an n here, this loop is actually only going to run 1000 times. Because we're starting at n- 1000, going up to n. So, there's only 1000 steps between n- 1000 and n, and we're going to do each step once. So this whole loop only runs 1000 times. So the total amount of work that it does, including its body, is just 1000 times the work of the body, which is n. So 1000 times n is just n times a constant, so we can replace that entire loop with the amount of work it does in big-O notation, and that's just order n again. Because again, it only ran 1000 times, which is a constant relative to n. So, now we have that the body of the outermost for loop is order n. So, let's count the times that the outermost for loop runs, and then we'll be able to assert how many times the entire block of code actually runs. So i this time starts at 0, and we go as long as i is less than 2*n, and we add one to i each time. So that's gonna be a total number of steps, total number of iterations of 2n, because we're starting at 0, going up to 2*n. So this outermost loop runs 2n times, it does order n work in its body, so now we have 2n times n gives us 2n squared. But in big-O notation, that 2 will go away, and we'll end up with the work being done by this entire block, is just order n squared.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. Tous droits réservés.

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales