Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. タイトル：
   Complete Graph Solution - Intro to Algorithms
2. 概説：

3. 0 0:00 - 0:04
   I told you to use a mathematical formula, so I cheated a little bit.
4. 4000 0:04 - 0:07
   I wrote a little piece of code to actually generate a complete graph
5. 7000 0:07 - 0:09
   and then return the number of edges in that graph.
6. 9000 0:09 - 0:12
   To make a complete graph, I just looped through all the pairs of nodes,
7. 12000 0:12 - 0:15
   and if one node was smaller than the other, then I made a link between them.
8. 15000 0:15 - 0:19
   That was mainly to just make sure I didn't make a link from nodes to themselves.
9. 19000 0:19 - 0:21
   There is no reason not to make a link the other way.
10. 21000 0:21 - 0:25
    It would have not counted against the total, but this seemed nicer and cleaner.
11. 25000 0:25 - 0:28
    Let's look at what happens if you loop on all the different values of n
12. 28000 0:28 - 0:33
    from 1 to 9 and print n and the number of edges in the clique.
13. 33000 0:33 - 0:35
    A graph with one node has no edges.
14. 35000 0:35 - 0:40
    A graph with 2 nodes fully connected has one edge, 3 has three--that's a triangle,
15. 40000 0:40 - 0:44
    4 has six, which is the square with the x through the middle of it,
16. 44000 0:44 - 0:48
    5 is that pentagram-looking thing that we just showed a minute ago,
17. 48000 0:48 - 0:50
    and it continues growing up like that.
18. 50000 0:50 - 0:52
    With that as our insight, can we actually write down what the formula is
19. 52000 0:52 - 0:54
    for a graph with n nodes?
20. 54000 0:54 - 0:58
    Essentially what happens is each node gets an edge to each other node,
21. 58000 0:58 - 1:02
    which we can write as each node has an edge to each other node.
22. 62000 1:02 - 1:06
    Notice what happens if we use that as our formula, we're going to count this edge,
23. 66000 1:06 - 1:08
    as it goes from this node to this node.
24. 68000 1:08 - 1:11
    We're also going to count it again, as it goes from this node to this node.
25. 71000 1:11 - 1:14
    We've double counted everything, so that should be our formula,
26. 74000 1:14 - 1:17
    which is Î(n²). Let's just double-check this.
27. 77000 1:17 - 1:21
    If we print n, clique (n), which I counted by actually creating the clique,
28. 81000 1:21 - 1:24
    compared that to the formula n * (n -1)/2,
29. 84000 1:24 - 1:26
    you can see that it matches up perfectly.
30. 86000 1:26 - 1:29
    So, really the answer that you should have given is this--
31. 89000 1:29 - 1:31
    shouldn't have bothered with any of this creating of stuff.
32. 91000 1:31 - 1:38
    Now, in addition to all those graphs where the growth rate was linear, we now have one that's quadratic.