## Worst Case Solution - Intro to Computer Science

• 0:00 - 0:04
So their answer is both of the last two. Both of
• 0:04 - 0:06
these will need to go through the loop here, the number of
• 0:06 - 0:09
elements in index times. In the case where it's a word that's
• 0:09 - 0:13
not in a index, the test will always be false, and will
• 0:13 - 0:15
get to the end of the loop and return none. In
• 0:15 - 0:19
the case where the last word is added, we'll still go through
• 0:19 - 0:22
the loop, the number of elements times, but the very last time
• 0:22 - 0:25
we'll find a match, and return that element. One of the assumptions
• 0:25 - 0:27
in all of this analysis is that the time it
• 0:27 - 0:30
takes to go through the loop doesn't depend on the actual
• 0:30 - 0:33
keyword that's passed in. And that's assuming that this equal
• 0:33 - 0:38
comparison takes the same amount of time depending on what the
• 0:38 - 0:41
entry and the keyword is. That it doesn't matter what
• 0:41 - 0:43
the keyword is the time to do this comparison is the
• 0:43 - 0:46
same. And it turns out that for strings and Python that's
• 0:46 - 0:50
the case. That we can do these string comparisons very quickly,
• 0:50 - 0:53
because strings are immutable. That means that we don't need to look
• 0:53 - 0:56
at all the characters in the string to compare two strings. That
• 0:56 - 0:59
double equal for strings can be done in such a way that
• 0:59 - 1:02
it doesn't need to look at the whole string. It knows that the
• 1:02 - 1:04
strings were created as different strings.
• 1:04 - 1:05
That means they're different strings. Or
• 1:05 - 1:09
if they were created as the same string, they're the same string. So
• 1:09 - 1:12
that's the reason why we say that all of the other operations
• 1:12 - 1:15
in the loop have constant time. That they don't depend on the size
• 1:15 - 1:19
of inputs at all. These are all very fast operations. What
• 1:19 - 1:22
matters in terms of understanding the time is the number of times
• 1:22 - 1:25
we go through that index. If you take the follow on course,
• 1:25 - 1:28
which I hope you will, we'll understand how to analyze algorithms in
• 1:28 - 1:31
a more formal way. For now our goal is to develop
• 1:31 - 1:35
an intuition, and for that intuition the important thing to understand is
• 1:35 - 1:37
the running time depends on the number of times we go through
• 1:37 - 1:41
this loop. Everything that we do inside the loop is constant time.
• 1:41 - 1:43
It's not affected by the size of the elements.
Cím:
Worst Case Solution - Intro to Computer Science
Leírás:

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS101 - Intro to Computer Science
Duration:
01:44
 Udacity Robot edited Angol subtitles for 18-15 Worst Case Solution Udacity Robot edited Angol subtitles for 18-15 Worst Case Solution Udacity Robot edited Angol subtitles for 18-15 Worst Case Solution Udacity Robot edited Angol subtitles for 18-15 Worst Case Solution Cogi-Admin edited Angol subtitles for 18-15 Worst Case Solution

# English subtitles

## Felülvizsgálatok Compare revisions

• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API