Return to Video

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:

18-15 Worst Case Solution

more » « less
Video Language:
English
Team:
Udacity
Projekt:
CS101 - Intro to Computer Science
Duration:
01:44

English subtitles

Felülvizsgálatok Compare revisions