Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
0
00:00:01,600 --> 00:00:07,599
In this clip, we will talk about asymptotic performance, which means not only to consider an expression or
1
00:00:07,599 --> 00:00:15,599
a curve that describes how execution time evolves for an algorithm, but also to only consider the significant
2
00:00:15,599 --> 00:00:22,600
paths of that expression, that is, the parts that constitutes the majority of the execution time.
3
00:00:22,600 --> 00:00:29,600
Consider this simple ccr function that initializes a calendar and keeps incrementing it with 1 and writing
4
00:00:29,600 --> 00:00:40,600
out its value until it reaches an upper limit, N. We can now ask, how complex is this function or algorithm?
5
00:00:40,600 --> 00:00:49,600
Let's count instructions. The initialization takes one instruction, the comparison inside the while
6
00:00:49,600 --> 00:00:58,600
condition also takes one instruction. For simplicity, we assume that the Console.WriteLine also consumes one
7
00:00:58,600 --> 00:01:07,599
instruction, and that the increment and assignment consumes one each, too.
8
00:01:07,599 --> 00:01:19,599
The loop is repeated N times, and the resulting expression can be shortened like this.
9
00:01:19,599 --> 00:01:27,599
If we draw that expression as a curve, it looks like this, a straight line.
10
00:01:27,599 --> 00:01:34,599
Take a look at this underlined 1. When N grows, that becomes quite insignificant.
11
00:01:34,599 --> 00:01:41,599
Also assume that our program was run on an iPhone and that the curve represents the execution time there.
12
00:01:41,599 --> 00:01:50,599
If we took the exact same function and ran it on the much faster laptop, the curve may have looked like this,
13
00:01:50,599 --> 00:01:57,599
still a straight line, but with a smaller slope. If we, for the sake of simplicity, say that the laptop is
14
00:01:57,599 --> 00:02:04,599
exactly twice as fast as the iPhone, which is an understatement to say the least, then the formula for the
15
00:02:04,599 --> 00:02:16,599
line would be 0.5 + 2N. So the number 4 we got when counting instructions can be considered scaled up and
16
00:02:16,599 --> 00:02:24,599
down, depending on which hardware that runs the code. And we can therefore ask if that constant helps
17
00:02:24,599 --> 00:02:28,599
understanding the nature of the performance behavior.
18
00:02:28,599 --> 00:02:37,599
So, it seems that the significant part of the expression for the execution time in this example is N times
19
00:02:37,599 --> 00:02:42,599
some constant factor where this constant factor depends on a number of things.
20
00:02:42,599 --> 00:02:48,599
For example, which hardware that runs the code. Let's consider a slightly more complex example with a
21
00:02:48,599 --> 00:02:55,599
function that iterates over all integer pairs for integers between 0 and N.
22
00:02:55,599 --> 00:03:02,599
Recognize the inner loop from the previous example. We already calculated the complexity of that.
23
00:03:02,599 --> 00:03:09,599
Also notice that the other loop is actually similar to the inner loop, and thus we also have an expression
24
00:03:09,599 --> 00:03:17,599
for the complexity of that. The only difference is that instead of calling Console.WriteLine, we execute the inner loop.
25
00:03:17,599 --> 00:03:24,599
Last we have a couple of initializations. Let's construct this a bit.
26
00:03:24,599 --> 00:03:37,599
1 + 1 = 2, 1 + 1 + 2 = 4, and 1 + 2 = 3. Let me remove all of these spaces, and multiply the N outside the
27
00:03:37,599 --> 00:03:47,599
parentheses with the 3 and 4N from inside the parentheses.
28
00:03:47,599 --> 00:03:54,599
If we draw this expression, the curve looks like this. Again, if that curve represents the execution time
29
00:03:54,599 --> 00:04:04,599
on the iPhone, and we also executed a similar function on the laptop, we get an expression like this.
30
00:04:04,599 --> 00:04:09,599
Again, we have the simplified assumption that the execution time is only cut in half on the laptop,
31
00:04:09,599 --> 00:04:16,600
but notice that the nature of the curve does not change when executing the program on a faster or slower machine.
32
00:04:16,600 --> 00:04:24,600
It only gets scaled by a constant factor, up or down. We can see, however, that whereas the previous example
33
00:04:24,600 --> 00:04:32,600
had a linear execution time, the execution time in this example is clearly dominated by the factor N squared.
34
00:04:32,600 --> 00:04:38,600
The takeaway from these two examples is that the constant factors may be overruled anyway by a change of
35
00:04:38,600 --> 00:04:44,600
execution hardware, so they may be omitted and we will still be able to get the interesting information about
36
00:04:44,600 --> 00:04:52,600
how the execution time grows with the input size. That is, when doing asymptotic performance analysis,
37
00:04:52,600 --> 00:04:59,000
we can ignore constant factors. And also as we shall see in a moment, we can actually focus on only the
38
00:04:59,000 --> 00:05:02,600
component in the instruction count expression with the highest order.
39
00:05:02,600 --> 00:05:08,000
In this example, the highest order component is N squared.
5220
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.