-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-10-1.html
285 lines (268 loc) · 11 KB
/
1-10-1.html
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="icon" href="./public/favicon.ico" />
<meta http-equiv="cache-control" content="no-cache" />
<title></title>
<link rel="stylesheet" href=" https://necolas.github.io/normalize.css/8.0.1/normalize.css" />
<link rel="stylesheet" href="./hightlight/default.min.css" />
<link rel="stylesheet" href="./css/main.css" />
<link rel="stylesheet" href="./css/copybutton.css" />
<link rel="stylesheet" href="./css/hightlight.css" />
<script src="./hightlight/hightlight.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.11/clipboard.min.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-BEVZJDBC7Z"></script>
<script src="./js/gtag.js"></script>
</head>
<body>
<header>
<nav>
<h1>
<span id="toggle-menu"></span>
<a href="index.html"></a>
</h1>
</nav>
</header>
<main>
<aside>
<nav></nav>
</aside>
<article>
<h2 id="1-10-1">1-10-1 Complexity and Big O Notation</h2>
<h3>Comparing Algorithms</h3>
<p>下列範例說明僅只是因為算法不同在相同的執行環境卻有性能上的差異。</p>
<pre><code class="language-js">
// 1 + 2 + 3 + ... + n = sum
function fun1(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
function fun2(n) {
return ((1 + n) * n) / 2;
}
let time1 = window.performance.now();
fun1(10000000);
let time2 = window.performance.now();
let timeDiff1 = (time2 - time1) / 1000;
console.log(`It takes ${timeDiff1} seconds to run fun1.`);
// Approximately 0.01723
let time3 = window.performance.now();
fun2(10000000);
let time4 = window.performance.now();
let timeDiff2 = (time4 - time3) / 1000;
console.log(`It takes ${timeDiff2} seconds to run fun2.`);
// Approximately 0.000065
</code></pre>
<p>
當我們在比較兩個不同演算法的時候主要考量兩個點-時間和空間。時間就如上範例所示比較時間的快慢，空間則是使用電腦多少記憶體。在分析時要排除硬體軟體效能的變因故產生出關鍵指標-「時間複雜度」、「空間複雜度」。
</p>
<h3>Complexity</h3>
<ul>
<li>加、減、乘、除、比較，都算作一個 Operation</li>
<li>給定一個 Input size 衡量一個演算法中用到多少 Operations</li>
<li>通常會用一個函式代號 f(n) 去表示 input size 和 複雜度總和。</li>
</ul>
<pre><code class="language-js">
function(n){
for (let i = 0; i < 3 * n; i++) {
console.log("Hello");
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log("Hello");
}
}
console.log("Hello");
console.log("Hello");
console.log("Hello");
console.log("Hello");
}
example(2);
// f(n)= n²+ 3n + 4
</code></pre>
<h3>用複雜度的概念分析第一個範例</h3>
<pre><code class="language-js">
function fun1(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
// f(n)= 3n
function fun2(n) {
return ((1 + n) * n) / 2;
}
// f(n) = 3
</code></pre>
<p>
將上面案例中兩個
<code>function</code>
的複雜度函式製作成xy座標軸平面圖將會看到在 n 值小的時候兩者並無顯著複雜度的區別,然而隨著 n
值越大兩者的複雜度差距則會越大。
</p>
<h3>Big O Notation</h3>
<p>
Big O 是一種描述 一個演算法 的 input n 越大則相對應的時間複雜度 f(n)
會如何變化的工具，展示複雜度的趨勢，需要探討演算法使用過後最壞的情況是如何？。
</p>
<p>如果不了解 Big O 的概念則無法有效去優化演算法。</p>
<h4>計算 Big O</h4>
<ul>
<li>忽略 constant 常數</li>
<li>忽略 小運算項</li>
<li>忽略 log 的底數</li>
</ul>
<p>例題1：時間複雜度為f(n) = 3n 演算法的 Big O 值為何？答案： O(n)</p>
<p>例題2：時間複雜度為f(n) = 13n^3+6n+7 演算法的 Big O 值為何？答案： O(n³)</p>
<p>例題3：時間複雜度為f(n) = 4log₂n 演算法的 Big O 值為何？答案： O(log n)</p>
<p>例題4：時間複雜度為f(n) = 5 演算法的 Big O 值為何？答案： O(1)</p>
<h4>常見演算法的 Big O 值</h4>
<p>由好到壞依序為：</p>
<ol>
<li>✔️ O(1)</li>
<li>✔️ O(log n)</li>
<li>✔️ O(n)</li>
<li>✔️ O(n log n)</li>
<li>✖️ O(n²)</li>
<li>✖️ O(n³)</li>
</ol>
<h3>深入解析 Big O 定義</h3>
<p>
function f(n) = O(g(n))。 iff(if and only if) ∃ (存在) C , n₀ . S.T.(使之受限於) 0 ≤ f(n)
≤ C∙g(n) ,(則) ∀ (對所有) n ≥ n₀
</p>
<p>
上面一段數學定義說的是：假如存在某實數 C , n₀， 使之受限於 0 ≤ f(n) ≤ C∙g(n), 對於所有的 n
≥ n₀。就可以說 function f(n) = O(g(n))。
</p>
<p>看起來不太直觀，我們可以舉一個例子並且畫一個座標平面圖說明：</p>
<p>
先進入
<a href="https://www.desmos.com/calculator?lang=zh-TW" target="_blank">繪圖計算機</a>
</p>
<p>假定有一個實數 C = 7 , g(n) = n</p>
<p>輸入第一個演算法：f(x) = 3x +6</p>
<p>輸入第二個演算法：g(x) = 7x</p>
<p>可以得出交會點 (1.5 , 10.5)</p>
<p>由此可得知 n₀ = 1.5</p>
<p>對於所有的橫軸 n ≥ n₀ 條件下，所有 C∙g(n) 的值會 ≥ f(n)</p>
<p>也因為我們找到了 n₀ , 結論推導： f(n) = O(g(n)) = O(n)</p>
<p>將算法換成 BigO 表示則 f(x) = 3x + 6 = f(n) = 3n+6</p>
<p>第二個例子：</p>
<p>假定有一個常數 C = 1 , g(n) = n²</p>
<p>輸入第一個演算法：f(x) = 3x +6</p>
<p>輸入第二個演算法：g(x) = 7x</p>
<p>由此可得知 n₀ = 4.372</p>
<p>對於所有的橫軸 n ≥ n₀ 條件下，所有 C∙g(n) 的值會 ≥ f(n)</p>
<p>也因為我們找到了 n₀ , 結論推導： f(n) = O(g(n)) = O(n²)</p>
<p>由此可以看出 Big O 求的是一個演算法最糟的情況。</p>
<h3>深入解析 Big Omega Ω 定義</h3>
<p>
function f(n) = Ω(g(n))。 iff(if and only if) ∃ (存在) C , n₀ . S.T.(使之受限於) 0 ≤ f(n)
≤ C∙g(n) ,(則) ∀ (對所有) n ≥ n₀
</p>
<p>
上面一段數學定義說的是：假如存在某實數 C , n₀ ， 使之受限於 f(n) ≥ C∙g(n) ≥ 0, 對於所有的
n ≥ n₀。就可以說 function f(n) = Ω(g(n))
</p>
<p>看起來一樣不太直觀，我們可以舉一個例子並且畫一個座標平面圖說明：</p>
<p>
先進入
<a href="https://www.desmos.com/calculator?lang=zh-TW" target="_blank">繪圖計算機</a>
</p>
<p>假定有一個實數 C = 1 , g(n) = log n</p>
<p>輸入第一個演算法：f(x) = 3x +6</p>
<p>輸入第二個演算法：g(x) = log x</p>
<p>可以看出 f(x) 的圖形一直位於 g(x) 的上方。</p>
<p>由於沒有焦點，所以假定 n₀ = 0</p>
<p>對於所有的橫軸 n ≥ n₀ 條件下，所有 C∙g(n) 的值會 ≤ f(n)</p>
<p>所以可以得出結論： f(n) = Ω(g(n)) = Ω(log n)</p>
<p>由此可以看出 Big Omega Ω 跟 Big O 概念相反。Big Omega Ω 求的是一個演算法優化的極限。</p>
<p>第二個例子：</p>
<p>假定有一個常數 C = 1 , g(n) = n</p>
<p>輸入第一個演算法：f(x) = 3x +6</p>
<p>輸入第二個演算法：g(x) = x</p>
<p>可以得出交會點 (0 , 6)</p>
<p>由此可得知 n₀ = 0</p>
<p>對於所有的橫軸 n ≥ n₀ 的條件下，所有 C∙g(n) 的值會 ≤ f(n)</p>
<p>
結論推導：因為 f(n) = Ω(g(n)) = Ω(n)，所以在 f(n) = 3n + 6 條件下可以找到一個 C 值使得f(n)
= Ω(n) ,f(n) = Ω(log n)，或者 f(n) = Ω(1)。
</p>
<h3>深入解析 Big Theta θ 定義</h3>
<p>
function f(n) = θ(g(n))。 iff(if and only if) ∃ (存在) C₁ ,C₂ , n₀ . S.T.(使之受限於) 0 ≤
C₁∙g(n) ≤ f(n) ≤ C₂∙g(n) ,(則) ∀ (對所有) n ≥ n₀
</p>
<p>
上面一段數學定義說的是：假如存在某實數 C₁ ,C₂ , n₀， 使之受限於 0 ≤ C₁∙g(n) ≤ f(n) ≤
C₂∙g(n)。就可以說 function f(n) = θ(g(n))
</p>
<p>看起來一樣不太直觀，我們可以舉一個例子並且畫一個座標平面圖說明：</p>
<p>
先進入
<a href="https://www.desmos.com/calculator?lang=zh-TW" target="_blank">繪圖計算機</a>
</p>
<p>假定有實數 C₁= 1 ,C₂ = 10 , g(n) = n</p>
<p>輸入第一個演算法：f(x) = 3x +6</p>
<p>輸入第二個演算法：g(x) = x</p>
<p>輸入第三個演算法：g(x) = 10x</p>
<p>看圖可以發現當 x ≥ 0.857 時，f(n) = 3x +6 會介於 g(x) = x、 g(x) = 10x 之間。</p>
<p>有滿足定義條件，故可以說 f(n) 的 Big Theta 為 θ(n)。</p>
<h3>Javascript 中 Object Array 的 Big O</h3>
<h4>Object</h4>
<p>
JS 中 Object 已經默認被轉換為 hash table 的型態，因為 hash table 的 Big O
值比較好。以下列舉操作 JS Object 動作所對應的 Big O 值。
</p>
<ul>
<li>Insertion - O(1)</li>
<li>Removal - O(1)</li>
<li>Searching(find key) - O(1)</li>
<li>Accessing(find value) - O(1)</li>
</ul>
<h4>Array</h4>
<ul>
<li>
Insertion -
<ul>
<li>push() - O(1)</li>
<li>unshift - O(n)</li>
</ul>
</li>
<li>
Removal -
<ul>
<li>pop() - O(1)</li>
<li>shift - O(n)</li>
</ul>
</li>
<li>Searching - O(n)</li>
<li>Accessing - O(1)</li>
</ul>
<pre><code class="language-js">
let n = 10
let arr =[1,2,3,4,5]
for(let i =0; i<n;i++){
arr.push(i) // O(1)
} // O(n)
for(let i =0; i<n;i++){
arr.unshift(i) // O(n)
} // O(n²)
</code></pre>
<p>
<a href="https://www.desmos.com/calculator?lang=zh-TW" target="_blank">繪圖計算機</a>
</p>
</article>
</main>
</body>
<script type="module" src="./js/main.js"></script>
</html>