| 常問為甚麼,有益身心健康;要訓練把解題流程標準化
一、QA 時間
為甚麼要會寫程式?
因為要讓電腦去執行我們的想法
甚麼是寫程式?
對電腦下指令,讓電腦照我的指示做
為甚麼需要程式碼?
因為電腦很笨,電腦只認得標準化的規則也就是程式碼,要跟電腦說相同的語言他才聽得懂
為甚麼不同的程式語言,電腦聽得懂?
範例(一)
二、內網/外網
- VPN概念說明 : 先連到某個地方,再連到某個地方
三、演算法
演算法為解決問題的方法。透過執行步驟與資料量n的關聯去衡量演算法的效率
如何衡量演算法好壞
- 時間複雜度 : 一個演算法平均需要多少時間完成。假設有 n 個數字,這個演算法平均要找 n 次,時間複雜度就是 O(n) (讀音 : BIG O ),執行所需時間與資料量 n 的關聯
- O(1) 執行所需步驟跟 n 沒有關係
- O(n) 執行所需步驟跟 n 成正比
- O(n^2) 執行所需步驟跟 n^2 成正比
- 空間複雜度 : 一個演算法平均需要多少空間完成。執行所需空間與資料量 n 的關聯
一、搜尋方式
ex(1) : n 個數字 m 次查詢
1) 已知 : 輸入 1,3,4,5,9,10
2) 所求 : 找出有無 9,20,30
- 演算法(一) : 從頭找到尾,輸出=有、無、無。 m 次查詢每次要找 n 個數字,時間複雜度=O(n * m)
- 演算法(二) : 建立 table 表。 n 個數字要填表需要 n 個步驟, m 次查詢每次只要一個步驟,時間複雜度=O(n + m)
從演算法(一)到演算法(二),以空間換時間
ex(2) : binary search (二分搜尋法)
1) 原理 : 類似終極密碼。先藉由排序過的序列特性,從中間切切切,不必從頭到尾一直找數字。
2) 程式碼 :
二、排序方式
ex(1) : selection sort
1) 原理 : 選擇每次裡面最小的元素,和第一個元素進行位置交換。再從剩下的數列中,重複上述動作
2) 程式碼 :
ex(2) : bubble sort
1) 原理 : 由左到右兩兩比較,把比較大的數字右移。可以想像比較大的數字會浮上來。第一輪執行完後會確定,最右側的數字為數列中的最大值。
2) 程式碼 :
ex(3) : insertion sort
1) 說明 : 玩撲克牌時會用到的排序方式。從最左邊開始,把數字一個一個比對,插入已經排好的數列中
2) 程式碼 :
ex(4) : merge sort (合併排序法)
1) 說明 : 把一個數列分成左右兩半,個別排序後再合併起來
- step 1 : partition 分組
- step 2 : sort 排序
2) 原理 :
3) 程式碼 :
ex(5) : quick sort
1) 說明 : 挑選一個基準點(pivot),讓左邊的數字都小於它,右邊的數字都大於它,對左右兩邊重複這項操作
2) 程式碼 :