Measuring Time - Intro to Algorithms Udacity English (auto-generated) English

Measuring Time - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 7.3K views 3 likes 0 dislikes 27 Jun 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

one of the things we'd like to do is have a way of comparing algorithms in

One of the things we'd like to do is have a way of comparing algorithms

terms of the time it takes to run them

in terms of the time it takes to run them without actually having to go and do

without actually having to go and do all the hard work of running them instead

all the hard work of running them.

what we're gonna try to do is analyze

Instead what we're going to try to do is analyze what the running time is

what the running time is in kind of more of an abstract model of computation to

in more of an abstract model of computation.

do that is very difficult to get the

To do that is very difficult.

exact timing information without

To get the exact timing information without actually running it

actually running it is something that we

is something that we probably can't do.

probably can't do but we can make a series of simplifying assumptions these

But we can make a series of simplifying assumptions.

simplifying assumptions will allow us to do an analysis that is more tractable so

These simplifying assumptions will allow us to do an analysis that is more tractable.

here's some of the assumptions that

Here are some of the assumptions that we're going to make.

we're gonna make so we count a simple statement something like x equals x plus

We count a simple statement--something like x = x + 1

1 as something that takes one unit of

as something that takes 1 unit of time.

time and we're gonna count up the number of units of time an algorithm takes to

We're going to count of the units of time that an algorithm takes to run.

run the second simplifying assumption we'll make is that the time it takes to

The second simplifying assumption we'll make is that the time it takes to execute

execute a pair of statements or three statements or ten statements in sequence

a pair of statements or three statements or ten statements in sequence

is the sum of the times that it takes to

is the sum of the times that it takes to execute each of the individual statements.

execute each of the individual statements so this ignores a lot of issues that go on in the architecture of

This ignores a lot of issues that go on in the architecture of the computer--

the computer things like pipelining and caching that make this actually not true

things like pipe-lining and caching--that make this actually not true in practice.

in practice but we're gonna hope that it's a good enough approximation of

But we're going to hope that it's a good enough approximation of reality.

reality so measuring the time that takes

Measuring the time that it takes to run something like an if statement,

to run something like an if statement we're gonna imagine that there's the time that it takes to execute the condition evaluation and then the time

we're going to imagine that there's the time that it takes to execute the condition evaluation

that it takes to actually execute the

and then the time that it takes to actually execute the statement.

statement so this would be essentially

This would be essentially 2 units of time.

two units of time so it follows from these assumptions that the running time for a loop is going to be equal to the

It follows from these assumptions that the running time for a loop is going to be equal

time it takes for the body of the loop to run times the number of times its

to the time it takes for the body of the loop to run times the number of times it's repeated--

repeated the number of iterations so a

the number of iterations.

block of statements like this where I takes on a set of values 0 1 2 & 3 and

A block of statements like this where i takes on a set of values 0, 1, 2, and 3

prints each one will say that this takes

and prints each one--we'll say that this takes 4 units of time,

4 units of time because this unit statement is repeated four times so

because this unit statement is repeated 4 times.

let's see if you're getting the hang of

Let's see if you're getting the hang of this. Here's a little quiz.

this so here's a little quiz how many units of time will this little block of

How many units of time will this little block of Python code take to run?

Python code take to run can fill in your numerical answer in the box

Fill in your numerical answer in the box.

Similar videos:

Algorithms Are Cool - Intro to Algorithms
Udacity
5.4K views 12 likes 0 dislikes 27 Jun 2012100% match

Build Heap - Intro to Algorithms
Udacity
20.8K views 75 likes 4 dislikes 19 Jul 2012100% match

Making a SAT graph - Intro to Algorithms
Udacity
3.4K views 18 likes 0 dislikes 23 Feb 2015100% match

Properties of Social Networks - Intro to Algorithms
Udacity
4.2K views 14 likes 2 dislikes 23 Feb 2015100% match

Connected Components - Intro to Algorithms
Udacity
18.9K views 16 likes 35 dislikes 23 Feb 2015100% match

Order Statistics - Intro to Algorithms
Udacity
5.4K views 6 likes 9 dislikes 19 Jul 2012100% match

Counting Steps - Intro to Algorithms
Udacity
26.1K views 29 likes 60 dislikes 27 Jun 2012100% match

Create Graph With Eulerian Tour - Intro to Algorithms
Udacity
7.4K views 6 likes 1 dislikes 23 Feb 2015100% match

Magic Trick - Intro to Algorithms
Udacity
28.5K views 39 likes 6 dislikes 27 Jun 2012100% match

Russian Peasants Algorithm - Intro to Algorithms
Udacity
9.7K views 8 likes 2 dislikes 27 Jun 2012100% match

NP-Hard - Intro to Algorithms
Udacity
6.3K views 17 likes 3 dislikes 23 Feb 2015100% match

Case Study - Intro to Algorithms
Udacity
13K views 8 likes 0 dislikes 27 Jun 2012100% match

Top K Problem - Intro to Algorithms
Udacity
6.2K views 11 likes 8 dislikes 19 Jul 2012100% match

Non-deterministic Polynomial Time Decidable Problem - Intro to Algorithms
Udacity
4.1K views 16 likes 11 dislikes 23 Feb 2015100% match

Clique Problem - Intro to Algorithms
Udacity
8K views 11 likes 7 dislikes 23 Feb 2015100% match

Divisible By Five - Intro to Algorithms
Udacity
4.4K views 2 likes 8 dislikes 29 Jun 2012100% match

Exponential Running Time - Intro to Algorithms
Udacity
4.8K views 12 likes 10 dislikes 23 Feb 2015100% match

Reduce 3-Colorability to SAT - Intro to Algorithms
Udacity
11.8K views 53 likes 8 dislikes 23 Feb 2015100% match

Correctness: Naive - Intro to Algorithms
Udacity
10.6K views 41 likes 2 dislikes 27 Jun 2012100% match

Introduction - Intro to Algorithms
Udacity
35.6K views 113 likes 1 dislikes 27 Jun 2012100% match

Finding Bridge Edges - Intro to Algorithms
Udacity
7.8K views 21 likes 20 dislikes 23 Feb 2015100% match

Recurrence Relation - Intro to Algorithms
Udacity
6.3K views 7 likes 1 dislikes 27 Jun 2012100% match

Longest Simple Path - Intro to Algorithms
Udacity
17.4K views 32 likes 27 dislikes 23 Feb 2015100% match

Bridge Edges - Intro to Algorithms
Udacity
4.2K views 20 likes 5 dislikes 23 Feb 2015100% match

Graph Coloring is NP-Complete - Intro to Algorithms
Udacity
10.1K views 20 likes 12 dislikes 23 Feb 2015100% match

Running Time - Intro to Algorithms
Udacity
9.8K views 12 likes 1 dislikes 27 Jun 2012100% match

Hypercube - Intro to Algorithms
Udacity
13.8K views 86 likes 5 dislikes 29 Jun 2012100% match

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Divide And Conquer - Intro to Algorithms
Udacity
35.1K views 141 likes 15 dislikes 27 Jun 2012100% match

Eulerian Path - Intro to Algorithms
Udacity
55.8K views 144 likes 30 dislikes 27 Jun 2012100% match

Settings Privacy About Contact Donate