Running Time - Intro to Algorithms Udacity English Japanese

Running Time - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 9.8K views 12 likes 1 dislikes 27 Jun 2012

Udacity 651K subscribers United States YouTube↗

Click to Play Video

What I'd like you to think about is how long does it take for naïve(a, b)

naive(a,b)に大きい数値を当てはめたら実行するのに

to execute as we look at larger and larger inputs.

どれくらい時間がかかるか考えてみてください

These should be really fast. This should still be pretty fast.

これらは速いでしょう　これも速いでしょう

As we give it larger and larger powers of 2,

より大きい数値を当てはめれば

you should notice that it's going to take longer and longer for this multiplication to actually execute.

計算により長い時間がかかることが分かるはずです

Now, I could keep doing this all day, which probably wouldn't be fun for any of us.

これを一日中続けても面白くないでしょう

What I'll do instead is have the computer actually do some of these calculations for me.

代わりにコンピュータにこれらの計算をしてもらい

I'll measure the time and then we'll plot it and see how it turns out.

かかった時間を計りグラフに表します

Here's our naïve algorithm again.

これはアルゴリズムnaiveです

There's a whole lot of Python code wrapped around it that's going to help us do some plotting

前後にあるのはグラフを作成するためのPythonコードです

What we're going to do is we're going to run naïve(n, n) with different values of n.

nに様々な値を当てはめnaive(n,n)を実行します

The n's are going to be all the powers of 2 from 2^0 to 2^23.

nには2の0乗から23乗までのすべての数値を当てはめます

For each of those what we're going to do--and the details of this aren't important--

それぞれの数値を当てはめた計算について

we're going to time how long it takes to do that, gather all those times together,

かかった時間を計測しデータを集め

and then plot them. Here we go. We run this.

集めたデータをグラフにします　では実行します

It generated a plot, and this is what that plot looks like.

グラフができました　こちらです

It's a little bit crufty to read at the bottom,

下の部分が見にくいですが

but you can get a sense of the general shape of it.

どんな形かは大体分かるはずです

Across this access is the number that we're squaring.

横軸は2乗した数値です

We're sending naive of this number, and it goes up to billions.

ゼロから何百万までに渡ります

This is the time in seconds that it takes for it to execute.

縦軸は実行するのにかかった時間です

You can see that it actually follows a very recognizable pattern.

グラフの形は非常に分かりやすいです

Our plot looks something like this.

ちょうどこんな形です

How does the running time t relate to the input that we're giving naive n?

nに当てはめた数値と実行時間tの関係はどうなっているでしょうか

Is the running time roughly constant-- as n gets bigger the time stays about the same?

実行時間は一定で nが大きくなっても変わらないでしょうか

Is it roughly logarithmic--as n gets bigger the time grows like the log of n?

それともnが増えると実行時間も対数関数的に増加するのでしょうか

Is it roughly linear--as n gets bigger the time grows like cn for some constant c?

それともnの増加に比例して実行時間も長くなるのでしょうか

Or is it roughly exponential where the time grows like c^n for some value of c?

または指数関数のように実行時間もcのn乗となるのでしょうか

Similar videos:

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

Erdos Renyi - Intro to Algorithms
Udacity
7K views 20 likes 2 dislikes 23 Feb 2015100% 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

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

Clique Problem in NP? - Intro to Algorithms
Udacity
5.3K views 15 likes 3 dislikes 23 Feb 2015100% 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

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

Big-Theta Examples - Intro to Algorithms
Udacity
17.9K views 80 likes 102 dislikes 29 Jun 2012100% match

Reduce SAT to 3-Colorability - Intro to Algorithms
Udacity
10.8K views 14 likes 84 dislikes 23 Feb 2015100% match

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

Eulerian Path - Intro to Algorithms
Udacity
5.2K views 2 likes 0 dislikes 27 Jun 2012100% match

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

Eulerian Path Solution - Intro to Algorithms
Udacity
15.9K views 64 likes 1 dislikes 27 Jun 2012100% 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

Steps For Naive - Intro to Algorithms
Udacity
5.7K views 1 likes 0 dislikes 27 Jun 2012100% match

NP-Completeness - Intro to Algorithms
Udacity
8.9K views 30 likes 9 dislikes 23 Feb 2015100% match

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

Clique Problem - Intro to Algorithms
Udacity
26.6K views 82 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

Lower Bound on Complexity - Intro to Algorithms
Udacity
11.9K views 21 likes 23 dislikes 23 Feb 2015100% match

Degree Centrality - Intro to Algorithms
Udacity
7K views 5 likes 5 dislikes 19 Jul 2012100% match

Pathway That Can Use Two Nodes - Intro to Algorithms
Udacity
19.5K views 408 likes 7 dislikes 08 Aug 2012100% match

Code for Dijkstra - Intro to Algorithms
Udacity
9.9K views 20 likes 4 dislikes 23 Feb 2015100% 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

Matrix Multiplication - Intro to Algorithms
Udacity
6K views 8 likes 7 dislikes 23 Feb 2015100% match

Settings Privacy About Contact Donate