visual-complexity-main/index.html at master · MattKovtun/visual-complexity-main · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <link href="https://fonts.googleapis.com/css?family=Arvo|Lato" rel="stylesheet">

    <title>Visual difference in complexity</title>
</head>
<body class="page">
<h2 class="page__tittle">Page created to visualise difference of complexity of solving the same task</h2>
<article class="article">
    <h3 class="article__tittle">Introduction</h3>
    <p class="article__text">
        It was the end of the 2nd educational year at Ukrainian Catholic University, beginning of a summer.
        I passed all my exams and naturally had a free time, so I was looking for a job.
        I had a couple of interviews in different companies where I had to solve different tasks.
        This page is dedicated to one interesting task I had to solve.
    </p>
    <h3 class="article__tittle">Main</h3>
    <p class="article__text">
        I came to an interview and guys gave this task to solve.
    </p>
    <h4 class="article__tittle article__tittle_bold">Task</h4>
    <p class="article__text">
        Exists an array with 99 numbers ranged from 1 to 100, all entries are different.
        One number is missing to complete the set of 100 numbers.
        Find this number.
    </p>
    <h4 class="article__tittle article__tittle_bold">Task: Modified</h4>
    <p class="article__text">
        This task wasn't really interesting so I modified it a bit,
        to be a little bit more complex and thought-provoking.
        Exists an array with 99 numbers ranged from 1 to 100, entries can be same.
        Some numbers are missing to complete the set of 100 numbers.
        Find numbers which are missing and count occurrence of each present number.
    </p>
    <h3 class="article__tittle">Approaches</h3>
    <pre class="article__approaches article__approaches_slow"><code>RES = [ ]
FOR i = 1 TO N
    COUNT = 0
    FOR j = 0 TO N - 1
        IF i == numbers[ j ]
            COUNT++
    RES.add( i, COUNT )</code></pre>
    <p class="article__text">
        Rough complexity of this approach is O(n&sup2;&middot;K&middot;C), where K is time to perform one action.
    </p>
    <pre class="article__approaches article__approaches_fast"><code>RES = [ ]
COUNTER = [ N elements ]
FOR i = 0 TO N - 1
    COUNTER[ numbers[ i ] - 1 ]++
FOR i = 0 TO N
    RES.add( i + 1, COUNTER[ i ] )</code></pre>
    <p class="article__text">
        Rough complexity of this approach is O(2&middot;n&middot;K&middot;C), where K is time to perform one action.
        However, this approach needs additional memory equal to O(n).
    </p>
    <p class="article__text">
        In this illustration we've taken K equal to <span class="article__k"></span>sec.<br>
        At the end we multiply everything by C, which represents load of PC, speed of running code, speed of erasing
        SVG, speed of incrementing variable...<br>
        One empty object in array takes 65.72 bytes.<br>
        Number of points, n = <span class="article__points">100</span>.
    </p>
    <p class="article__approaches article__approaches_slow">
        O(n&sup2;&middot;K&middot;C) = <span class="article__points">100</span>&sup2; &middot; <span
            class="article__k"></span>
        &middot; C
        &asymp; <span class="article__result_bad">10</span> &middot; C <br>
        Additional memory ~ 0 mb<br>
    </p>
    <p class="article__approaches article__approaches_fast">
        O(2&middot;n&middot;K&middot;C) = 2 &middot; <span class="article__points">100</span> &middot; <span
            class="article__k"></span> &middot; C
        &asymp; <span class="article__result_good">0.2</span> &middot; C<br>
        Additional memory ~ <span class="article__memory"></span> mb<br>
    </p>
</article>
<div class="page__content">
</div>
<div class="settings"><input class="settings__points" type="range" min="0" max="400"
           step="1" value="100">
<button class="settings__start-button">START</button>
</div>

<section class="result">
</section>
<article class="article article_conclusion">
    <h3 class="article__tittle">Conclusion</h3>
    <p class="article__text">
        The purpose of this page was not to teach anyone with new algorithms.
        The only purpose was to encourage the reader to think first what rather has to be sacrificed either speed or
        memory.
    </p>
</article>
<script src="build/bundle.js"></script>
</body>
</html>