Shadowing-Übung: What Is Dynamic Programming and How To Use It - Englisch Sprechen Lernen mit Video

Übungsmodus wählen

Jeder Modus öffnet einen Übungsraum im Vollbild.

175 Sätze
Wenn Sätze zu kurz oder zu lang sind, klicke auf Edit, um sie anzupassen.
1
Hey CSDojo, it's YK here.
2
So in this video I'm going to talk about what dynamic programming is
3
and how to use it and as I explain how it works I'm going to assume that you're already familiar with recursion.
4
So what is dynamic programming exactly?
5
It's actually fairly simple even though it might sound difficult
6
It's basically a way of making your algorithm more efficient by storing some of the intermediate results
7
And it works really well when your algorithm has a lot of repetitive computations
8
So that you don't have to repeat those computations over and over again and
9
I'm gonna give you a concrete example of how it works with Fibonacci sequence
10
So just in case you're not familiar with it Fibonacci sequence is a sequence of numbers
11
that starts with two ones at the beginning and Each number after that is computed by adding up the two previous numbers
12
So the third Fibranch number is 2 because 1 plus 1 equals 2
13
And then the fourth Fibranch number is 3
14
because 1 plus 2 equals 3 and so on and this sequence keeps on going forever
15
So let's say we're trying to solve the problem of finding the n's Fibranch number
16
or writing a function called Fib of n
17
Which takes a positive integer n and finds and returns the n's Fibranch number
18
So if the given n is 3
19
We want to be able to find and return the third free lunch number, which is 2
20
And if the given n is 5, we want to be able to return the fifth free lunch number, which is 5
21
Let's see how we can solve this problem using dynamic programming
22
So if you want to solve a problem using dynamic programming, there are typically three steps you can take
23
The first step is to come up with a recursive solution to your problem
24
And then in your recursive solution, if you notice that there are a lot of repeated computations
25
You can then store some of the intermediate results so that you don't have to repeat those computations
26
This process is also called
27
Memoization or memoize and this is not to be confused with Memorize
28
and I've made that mistake before too and then the third step if you don't like using recursion anymore is
29
To come up with something called a bottom -up approach
30
So let's first see what a recursive solution might look like for this particular problem
31
So as I said earlier, we're going to write a function called fib of n
32
Which takes n a positive integer and returns the nth fibranche number
33
And if n is equal to 1 or 2
34
We know that the first and the second fibranche numbers are 1
35
We're going to return 1
36
But instead of returning it right away
37
We're going to store it in a temporary variable called the result and then return that instead.
38
And it's going to be clear why we need to do that later.
39
And if n is neither 1 nor 2, then we're going to return the sum of the two previous Fibonacci numbers instead.
40
Fib of n minus 1 plus Fib of n minus 2, store that in result, and then return it at the end.
41
So this solution works, but it's very very inefficient.
42
To see why, let's see an example where we are trying to find the fifth Fibonacci number by calling Fibonacci 5.
43
So to find the return value of Fibonacci 5,
44
we need to first compute the return values for Fibonacci 4 and Fibonacci 3 so we can add them up.
45
And to find Fibonacci 4, we need to first compute Fibonacci 3 and Fibonacci 2 and so on.
46
And that's what this diagram shows.
47
And looking at this diagram, you might notice that there are some competitions that we repeat over and over again.
48
For example, we need to compute the return value for Fibonacci 3 times,
49
and we need to compute the return value for Fibonacci 3 twice here.
50
And it's not a big deal when we are trying to find the 5th or 6th Fibonacci number,
51
but if we're trying to find the 100th Fibonacci number, it becomes an issue.
52
And actually the time it takes to find the n's Fibonacci number grows exponentially
53
Or roughly in the order of 2 to the power of n
54
And dynamic programming here says why not just store those return values
55
For example for Fibonacci 3 store the return value once we compute it
56
And then use that same value when we see Fibonacci 3 again instead of computing it again
57
And again, this process is called memoization.
58
So let's see what a memoized solution looks like in code
59
Let's again consider the example where we're trying to find the fifth few months number by calling Fib of 5
60
The idea of this solution is going to be that we're going to use an array whose length is
61
n plus 1 or 6 in this particular case
62
because n here is 5 and then we're going to store the return value for the functional fib of n.
63
at the index n.
64
So we're going to store fib of 1, which is the first fib of number right here at index 1,
65
and then fib of 2 at index 2, and so on.
66
And initially we're going to set all these values to null.
67
And we're going to write our function fib, and this is going to take two arguments instead of just one.
68
The first one is the same as before, n, a positive integer, and the second one is going to be this array
69
and so you'll need to initialize this array memo before you call this function.
70
Now at the beginning of this function, check if memo at index n is null or not.
71
If it's not equal to null, that'll mean that we've already seen this argument n and we've
72
We've already stored the return value for that at the index n in memo, so just return that instead
73
So return memo square brackets n
74
Otherwise, the following part is the same as before
75
If n is equal to 1 or 2, return 1, store 1 in result, and then return that at the end
76
And if that's not the case, then find the sum of the two previous equivalent numbers, and then return that instead
77
And then what's new in this function is that before you return this result, the return value
78
You need to store it in Memo at index n so that you can use it later
79
Let's now think about the time complexity for this solution.
80
We're going to call it t of n
81
This is going to be the time it takes to find the n's Fibonacci number with this particular method and
82
we're going to find that by multiplying the number of times we call this function,
83
fib, with the time it takes to execute each of those calls.
84
We're going to call that t.
85
Now, there are only two ways we're going to call this function fib.
86
The first way is when we call this function for the first time with the arguments n
87
and memo to find the entropy bunch number, and the second way is from this line right here,
88
and And notice that if you look at this whole block after this first if clause,
89
this whole block is only executed at most n times.
90
And this is true because there are n possible arguments to this function.
91
That's 1 through n.
92
And each time this function is called with each of those arguments, the return value will be stored in memo at index n.
93
So after the first time this function is called with each argument, we'll never get to this block.
94
And each time this block is executed, fib is called a most twice if we get to this line.
95
So the number of times fib is called is a most 2 times n plus 1.
96
So 2n comes from this block right here, and 1 comes from the first time we call this function fib and
97
the time it takes to execute each of those calls this t right here is
98
Going to be a constant time or a big O of 1
99
and this is because if you look at each operation in this function excluding
100
These recursive calls that follow each operation is a constant time operation and when you have a constant time operation
101
when you add them up, you still get a constant time operation, which is big O of 1.
102
And that's why we have big O of 1 here.
103
And so t of n, or the time it takes to find the n -spin -onage number with this particular method,
104
is going to be 2n plus 1 times big O of 1, which is big O of 2n plus 1,
105
which is equal to big O of n.
106
and this is a huge improvement from what we had earlier
107
which was big O of 2 to the power of n
108
and let's now examine how this memo array is actually filled
109
so let's say we're trying to find the fifth Fibonacci number again
110
and when we call fib with the argument 5
111
and memo of course we'll see
112
that we don't have a stored value at the index 5 yet
113
so we go down and we're gonna to ask ourselves what's the value of Fib of 4
114
and then 3 and so on and when we get to Fib of 2
115
we'll know that this value is 1 so we're going to store it at index 2 right here,
116
and same with Fibon1, that's 1 right here, and once we have these two values, we'll be able to find the third Fibonacci number,
117
which is Fibon3 right here, and then once we find the value by adding them up,
118
store that value right here so we can use it later, and then when we go up to Fibon4,
119
we'll add 1 and 2 right here and we get 3
120
and so on until we get here and
121
so as you can see this array is mostly filled from left to right so
122
when you see this you might say why not just explicitly build
123
this array from left to right from scratch instead of building it recursively
124
and that's the idea behind a bottom -up approach
125
so let's see what a bottom -up approach might look like in code
126
we're going to define a function called fib bottom up
127
which takes n a positive integer just like before
128
and returns the nth Fibonacci number and then
129
if n is equal to 1 or 2 of course we're going to return 1 and after
130
that we're going to define an array whose length is going
131
to be n plus 1 where n plus 1 is 6 of course
132
if we're trying to find the fifth Fibonacci number right here
133
if n is equal to 5 and after
134
that we're going to set the first and the second elements of this array bottom -up to be 1, these two items right here,
135
and then we're going to run a for loop for i from 3, which corresponds to this item right here,
136
up to n, and n corresponds to the last item right here of this array,
137
and whatever index we're examining currently we're going to set
138
that element at the index i
139
or bottom up square brackets i to be the sum of the two previous items
140
so in this particular example we'll have two here three here
141
and after that we're going to return the last item in bottom up
142
or bottom up square brackets n
143
and we're done the time complexity for this algorithm will be again big o of n
144
because we're going to define this array and go through this array only once
145
Okay, so that's how dynamic programming works
146
But now I'm gonna show you a quick demo with Python
147
and something called Jupyter Notebook to show you how this idea might play out in practice
148
So in this Jupyter Notebook, I have defined a few functions in Python Fib of n which is a recursive naive recursive solution and
149
Fib of memo and fib of 2 which represent a memoized solution and 5th bottom -up, which is of course a bottom -up solution.
150
So let's see how they compare to each other in performance
151
We're gonna try running fib of n first the naive recursive solution with fib of 5 and
152
That gives us 5 which is expected.
153
What about fib of 20?
154
That gives us the answer pretty quickly, too.
155
And what about fib of 35?
156
This actually takes 5 to 6 seconds on my computer
157
So it's obviously not the most efficient approach.
158
Let's see how fib of two and fib of memo the memoized solution compares to that
159
Let's try running fifth memo of five firsts and that gives us five which is expected
160
And what about fifth memo 35?
161
That's pretty quick, too.
162
And what about fifth memo 100 and 1000
163
This actually gives us an error and this error is called the recursion error
164
Python gives us this error actually because there are too many recursive calls on a call stack and
165
To fix that we can just use the bottom -up approach
166
One advantage of using a bottom -up approach is that we don't have to put any recursive calls on a call stack
167
So we don't have to worry about that.
168
So we're going to load this function and then run it with the argument 35
169
Which is pretty quick 1000 and then let's try 10 ,000 as well
170
And that's pretty instantaneous, too.
171
Okay, so that's my introduction to dynamic programming.
172
Let me know in the comment section below what you thought of this video,
173
and if you have any requests about what kind of videos I should make in the future,
174
let me know in the comment section below as well.
175
I'm YK from CSDojo, and I'll see you in the next video.

App herunterladen

Alles, was du zum fließenden Sprechen brauchst

KI-AussprachebewertungJeder Satz bewertet
IPA-TrainingJeden Laut meistern
WortschatzBaue deinen Wortschatz auf
VokabelspielSpielend lernen

Gleicher Kanal

FOR YOU

Empfohlenes Video

Wortschatz und Sprechhinweise zu dieser Lektion

Diese Sprechübung basiert auf dem Video „What Is Dynamic Programming and How To Use It“. Diese Wörter kommen am häufigsten vor: fib, return, Fibonacci, value, function. Dieses Video enthält 175 Sätze und 2286 Wörter zum Nachsprechen. Der gesprochene Teil dauert 14:27. Der Sprecher spricht in natürlichem Tempo, etwa 158 Wörter pro Minute, ähnlich wie im Alltagsgespräch. 85 % der Wörter gehören zu den 3.000 häufigsten im Englischen; den Rest solltest du dir vor dem Üben ansehen.

Wichtiger Wortschatz in diesem Video

15 lernenswerte Wörter aus dem Video, mit Aussprache und Bedeutung:

WortAusspracheBedeutung
memo Substantiv/ˈmɛməʊ̯/Memo, Notiz
array Substantiv/əˈɹeɪ/Bekleidung, Tracht
dynamic Adjektiv/daɪˈnæm.ɪk/dynamisch
sequence Substantiv/ˈsiː.kwəns/Reihenfolge
define Verb/dɪˈfaɪn/bestimmen
execute Verb/ˈɛksɪˌkjuːt/hinrichten, exekutieren
solve Verb/sɒlv/lösen
algorithm Substantiv/ˈælɡəɹɪðm̩/Algorithmus
bracket Substantiv/ˈbɹækɪt/Winkel, Träger
element Substantiv/ˈɛləmənt/Element
compare Verb/kəmˈpɛɚ/vergleichen, komparieren
efficient Adjektiv/ɪˈfɪʃənt/effizient
examine Verb/ɪɡˈzæmɪn/untersuchen
stack Substantiv/stæk/Stapel, Feime
complexity Substantiv/kəmˈplɛk.sɪ.ti/Kompliziertheit, Komplexität

Phrasal Verbs, die du hören wirst

WortBedeutung
come up with Verbausdenken
go down Verbabsteigen, hinabsteigen

Grammatik in diesem Video

Die Strukturen, die der Sprecher am häufigsten verwendet, mit den genauen Worten aus dem Video:

StrukturIm Video
Passiv be + Partizip Perfekt – wichtig ist, was geschieht, nicht wer es tutis computed · is also called · is called
Present Perfect have/has + Partizip Perfekt – eine vergangene Handlung, die jetzt noch wichtig istI've made · we've already seen · We've already stored
Relativsätze who / which + Satz – eine Zusatzinformation über eine Person oder Sachenumber, which is · operation, which is · five which is

Aussprache, auf die du achten solltest

Der Sprecher verwendet 62 Kurzformen und abgeschwächte Formen, zum Beispiel we're, don't, we'll. Sprich sie in der kurzen Form, so wie du sie hörst.

  • Die Laute „sh“ und „zh“: efficient /ɪˈfɪʃənt/, computation /ˌkɑmpjʊˈteɪʃn̩/, recursion /ɹɪˈkɜː(ɹ)ʒən/, memoization /ˌmɛmoʊaɪˈzeɪʃən/, exponentially /ɛkspə(ʊ)ˈnɛnʃəli/
  • Lange Wörter – auf die Betonung achten: intermediate /ɪn.tə(ɹ)ˈmi.di.ət/, complexity /kəmˈplɛk.sɪ.ti/, temporary /ˈtɛmp(əˌɹ)ɛɹi/, repetitive /ɹɪˈpɛtɪtɪv/, memoization /ˌmɛmoʊaɪˈzeɪʃən/

Laute, die Deutschsprachigen schwerfallen:

  • Stimmhafter Auslaut — /b/, /d/, /g/, /z/, /v/ am Wortende nicht verhärten: solve /sɒlv/, naive /naɪˈiv/, correspond /ˌkoɹəˈspɑnd/, confused /kənˈfjuːzd/, clause /klɔːz/
  • /æ/ — offener als „ä“: dynamic /daɪˈnæm.ɪk/, algorithm /ˈælɡəɹɪðm̩/, bracket /ˈbɹækɪt/, examine /ɪɡˈzæmɪn/, stack /stæk/

So übst du mit diesem Video

  1. Höre dir das ganze Video einmal an, ohne zu sprechen, und notiere die Wörter, die du nicht kennst.
  2. Beginne mit 0,75-facher Geschwindigkeit, sprich Satz für Satz nach und wechsle zur normalen Geschwindigkeit, sobald es leichtfällt.
  3. Nimm dich auf und vergleiche mit dem Original; achte dabei auf Wörter wie memo, array, dynamic.

Was ist die Shadowing-Technik?

Shadowing ist eine wissenschaftlich fundierte Sprachlerntechnik, die ursprünglich für die professionelle Dolmetscherausbildung entwickelt und durch den Polyglotten Dr. Alexander Arguelles populär gemacht wurde. Die Methode ist einfach aber wirkungsvoll: Du hörst englisches Audio von Muttersprachlern und wiederholst es sofort laut — wie ein Schatten, der dem Sprecher mit nur 1–2 Sekunden Verzögerung folgt. Anders als passives Hören oder Grammatikübungen zwingt Shadowing dein Gehirn und deine Mundmuskulatur, gleichzeitig echte Sprachmuster zu verarbeiten und zu reproduzieren. Studien zeigen, dass es Aussprachegenauigkeit, Intonation, Rhythmus, verbundene Sprache, Hörverständnis und Sprechflüssigkeit signifikant verbessert — was es zu einer der effektivsten Methoden für die IELTS Speaking-Vorbereitung und reale englische Kommunikation macht.

Shadowing-Technik: die vollständige Schritt-für-Schritt-Anleitung lesen →