4-Jul-2021
昨天看到一半睡了, 與其不知道自己攸甚麼不如今天來看好了
我想先整理一下Notes, 之後才開tutorial. 之前說要研究GitHub的take notes方法到今天還未看, 明天來研究好了。
這一課通用例子: 8個在門後的數字, 你要用不同的方法sort out他們
新工具
Duck debugging, ide 右上方多了一隻鴨子, 可以和他對話, 整理思緒。
Searching (搜尋的方法)
甚麼是searching? 你哪一個方法去找你某一個數值 →電腦一定是一個一個數值來看
現實化的話就像: array (一堆資料)→ black box(searching)→ output(bool, 他是/不是你要找的資料)
Running time: 在不同的數據量下, 找出你想找的數值的話要用多久 (可以是用不同的單位, 但我想多數會用steps的數量作準
Big O notation
該方法是如何根據數據量n的變化改變 →取最長的running time (upper boundary)
E.g. linear search → big O notation 會是n, 即使是用2n的方式來做linear search, 都只會是O(n), 因為running time的變化是受n(data size)的大小影響
用筆記上的graph來看的話, 如果你把圖片縮小來看, 你會發現n和2n的分別不大, 因為他們都只是根據n的大小的公式。log n也會是一樣的道理, 不論base是甚麼, log n 的graph都不會有太大的轉變。
有以下最常見的running times (由最長至最短) in big O notation:
O(n²)
O(n log n)
O(n) 每次一頁一頁地找人名
O(log n) 每次只保留有人名的一半
O(1) 不會在下表出現, 因為無論n怎樣變都只會是一樣的數 (constant number)
Big Omega notation(Ω)
以n作根據最短的running time (lower boundary)
例子: 在7個閉上的門之中找到最細的數字
my method: just check one by one from left to right (linear approach)
!!!!!!!!!要常常記得要多想想甚麼情況下會return false!!!!!!!
有以下最常見的running times (由最長至最短) in big Ω notation:
Ω(n²)
Ω(n log n)
Ω(n)
Ω(log n)
Ω(1) 在黃頁找人名的話會是這個, 因為可能第一頁就找到了
Binary search(logarithm)
Now use the log method, coz they are sorted
Pseudocode
O(log n) would be big O
Omega bound = Omega(1)
no doors would be return false
giga hertz per second(do giga things at one second)
Made numbers.c — implement linear search code
Exit status — tell the situation in you leave is success or not
Made names.c — to find the students name with same theory with numbers
!!原來當兩個都是string 的時候不可以用 == (cannot in C but can in Python)
//strcmp = can do the stuff for comparing string — only give out value
How to use it: strcmp(“first string”, “second string”) ==0
//if they are same,0; if first come before second in ASCII, then -ve;if second before first, then +ve
當在boolean loop中的括號是function的時候, ( )中的只是call of return value
Only zero is FALSE????????? Other will be true → 剛開始我聽不懂, 多想一下就想起了( )如果比較完出來的結果不是零, 就會以 if (-ve/+ve)的形式顯示, 即是會true; 反而Strcmp得出0的話, 就會是false
Non-zero = truthy
自制data type!! — 成為master!?!?!?!
例子 — 電話簿(名加數字) ←data structure (由你命名, 可以儲存多種data type)
點為何用string表示numbers? 因為有機會有 ‘-’ ‘,’ 等符號, 這堆數字亦不會用在算術中, 所以用string 反而會更好 — 現實生活中更常會以long來表達(信用卡)
Data type with some structure in it
可以用這個找到David的電話, 可是卻會有問題 — 電話和人對不起來, 如果你加了一個的數字, 就可能全錯? (人為錯誤的機會太多)
Better self-defensive
要留意的是person的做法就好像是array, 要先說明入面有甚麼類型的data type, 再以array型式
問題是這個方法去儲存data會很容易出錯, 萬一你一個資料錯了的話, 會很麻煩
Define the data type inside main function? — 可以, 但data type多數都會在Main上面的地方define, 因為想所有的function都可以使用那個data structure
可以在header中define data types和data structure嗎? — 會, 有在之後的堂中會, 目前只用了別人寫的
What if more ppl involved?
constant int 是一定要有的嗎?
不用linear search, use binary search
Selection sort
binary search →最好的
input(unsorted array 通常array就是一堆資料) → box →output(sorted)
為甚麼會用linear?
因為sorting是更複雜, rounding up/ down 會令你太難做(binary → 除二)
先不管準不準, 但少數量data會用linear, 因為binary可能還要debug
你要先想想你要的是減少run program的時間﹑減少debug的時間﹑還是memory的大小
但大部分都是要running time 要最少, ram used都是要最少
Spell checker → tool: 最少時間run, 最少memory take to run
Psuedo code:
to sort the number, it takes n-1 comparison where n = amount of left number to sort → selection sort
For i from 0 to n-1
Find smallest item between i th item and last item
Swap smallest item with i th item
可視化website, 模擬 selection sort的方法:
總共的steps: n+(n-1)+(n-2)…+1 =n(n+1)/2 =n²/2+n/2
Dominate factor: n²/2
Big-O : O(n²)
Lower bound: Omega-O: Omega(n²) ←即使是正確的排列法, 都要用這麼多的時間
如何改良?
Bubble sort
命字由來 → 最大的數會像泡泡一樣飄到最後
每次都compare兩個相鄰的數字, 將兩個數字按大小排列
how many comparison done: n-1
How many steps? (n-1)(n-1) =n²-2n+1
Repeat the steps of [for i from 0 to (n-2)] by(n-1)times
Big-O: O(n²)
Omega-O: Omega-O(n)
Pseudocode:
1. Repeat until sorted → (n-1) times
2. Range: for i from 0 to n-2 (Why??? → 0 is included so n-1, you compare it in pairs so need do n-2)
3. Compare i and i+1 value
4. Place them in order by swapping them
5. If no swaps
6.Quit
Still not good enough…
Recursion
ability of function call itself?????????
like main call main??
會不會無限loop? →會
但會更correct and better design
week 0 example: Open to middle of left half of book/Open to middle of right half of book → Search left half of the book/Search right half of the book
!!!!The input is different!!! HALF!!!!!!!!!
If the input is same
Base-case: if there are no problem to solve, quit
Example of pyramid in Mario → doing it layer and layer
Merge Sort
Add one special step → base case
If only one number
Quit
Sort left half
sort right half
merge sorted halves
Big O: n log base n
Omega O: n log base n
How to merge the sorted halves? by comparing the first one on each half
But how to sort? — also merge sort → the computer will then cut all number into half until the amount of number is 1 → where you need if one number, quit
At least one more array to store the information →more space required
Theta
Selection sort theta(n²)
Merge sort theta(n log n)
No matter is big O or omega, they are in same order