數值分析Q1補充

[aloh (aloh)]

※ 引述《y90633》之銘言：
: Q1.VP diagrams and Linked List
:         1.如何定義linked list 答題要寫程式碼
:         Ans. struct LLNode{
:                char key;
:                struct LLNode *next;
:              };
:         2.寫一個副程式去處理整串linked list裡的資料 (答題要寫程式碼)
:         Ans. 自己參考課本p.82
               如果照p82這個程式來講
               答案可以寫成
               struct LLNode *initLLNode(char val){
                 struct LLNode *temp;
                 temp=(struct LLNode *)malloc(sizeof(struct LLNode));
                 temp->next=NULL;
                 temp->key=val;
                 return(temp);
               }
               也就是在p83那個小小副程式啦

:         3.畫刪除linked list的節點的VP diagrams
:         Ans. 圖在課本p.79，如果是增加節點的話就是p.81的圖
: ======================================================================
: Q2.Time Complexity & Big-O
:         1.運算最快的排序演算法是什麼？Merge Sort屬於哪一種演算法？
:         Ans. Quick Sort.
:              Merge Sort屬於divide-and-conquer(分治法).
:         2.計算一個副程式的時間複雜度還有Big-O，這個副程式以遞迴的方式運行？
:         Ans. 這種題目會給一段程式碼然後要計算時間複雜度T(n)，以及O(n^2)
:              時間複雜度的計算方法要記一下：
:                 ( +, -, *, /) → 加減乘除，一個符號 = 1 unit.
:                 (declaration, function call, return) → 不計算 = 0 unit.
:                 ( ++, --) → 加加或減減 = 1 unit.
:              以下舉例，
:                 ex.(1) a = a^5  → 5 units.
:                        因為 a = a*a*a*a*a ，所以是5units.
:                    (2) a++j → 1 units. 這應該沒問題
:                    (3) a = (b-c)/d → 3 units.
:                    (4) for(j= 0; j<n; j++ ) → (2+2n) units.(不想理解就直接背
:                        因為 ↑    ↑    ↑                   ，反正可以帶筆記)
:                             1    (n+1)   n
:                        j<n會執行(n+1)次，所以就是n+1個units.
:                    (5) for(j= 0; j<n: j++ ){
:                          tot+= j;
:                          for(k= 0; k<n: k++ )
:                            tot+=k;
:                        };                   →2+6n+4n^2  units (應該是會考這種
:                                                                 題型)
:                        課本p.222頁有解釋，還蠻詳細的，用打的我也打不清楚，
:                        就自己看看課本不會再問我吧:)
:              以上都是計算時間複雜度T(n)的例子。
:              把T(n)算出來之後才有辦法求Big-O: O(n^2)，
:                 這個沒有標準答案，我舉個例子，過程差不多都是這樣
:                 ex. 假設T(n) = 3 + 6n + 4n^2
:                 Ans.    n       T(n)    5n^2    10n^2  ......
:                         1        13       5  <   10
:                         2        31      20  <   40
:                         3        57     458  <   90
:                         5       133     125     250
:                         7       241  <  245     490
:                         8       207  <  320     640
:                         T(n)< 10n^2，if n≧2
:                         所以O(n^2)  c=10  n=2.
:                也能寫成 T(n)< 5n^2 ，if n≧7
:                         所以O(n^2)  c=5   n=7.
:                所以沒有標準答案，算的出來就行。c是n^2的係數。
:         3.改寫這個程式以增加她的運算速度，答題要寫程式碼。
:         Ans.不會-.-
:         4.改進後的時間複雜度還有Big-O。
:         Ans.上面那題寫的出來的話，計算過程就跟Q2第2小題講的一樣算法。
: ======================================================================
: Q3.Searching & Sorting
:         1.Hash table 解釋什麼叫collision(碰撞)。
:         Ans.課本p272的方法就是了，照順序填入，如果位置有相衝，就擺在後一格。
:             只是大概敘述一下方法而已，答應應該沒這麼簡單。
:         2.舉三個解決collision的方法。
:         Ans.(1)Resolving collisions by replacement.
:             (2)Resolving collisions by open addressing.
:             (3)Resolving collisions by chaining.
:         3.計算Hash table，實驗課作過了。
:         Ans.(我真的不知道他在問啥)
: ======================================================================
: Q4.Searching & Sorting
:         1.QuickSort，實驗課做過了，可是題目有些微的差異，請注意看題目。
:         Ans.就是課本p.324的方法，大概敘述一下，配合p.328圖示講解來看比較
:             好看。
:             Step 1：取中間的那位字母，將他定為pivot。
:             Step 2：將pivot和字首的字母位置互換。
:             Step 3：從字首往字尾的方向找「比pivot大的字母」，
:                     從字尾往字首的方向找「比pivot小的字母」。
:             Step 4：將Step 3找到的兩個字母互換位置，
:                     若Step 3找到的兩個字母arrow across(交叉)(註1)，
:                     就將「比pivot小字母」的跟pivot換位置，並且變為新pivot。
:             Step 5：和pivot比較過的字母位置將會確定，之後將位確定位置的字母
:                     重複上述步驟。
: 註1：正常情況「比pivot大的字母」要在「比pivot小的字母」左邊，
:      若是相反，就是arrow across(交叉)。
:         2.Binary searches，實驗課做過。
:         Ans.(還不會)
:         3.如何「編譯」並「執行」一段程式碼。
:         Ans. (Compile)
:              gcc -c -ansi sdba.c
:              gcc -c -pedantic sdba.c
:              gcc -c -Wall sdba.c
:              (Link)
:              gcc -o sdba.exe sdba.o
:              (Run)
:              sdba
:              注意一下，sdba是檔案名稱，可以換。
: ======================================================================

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.138.247.59
→ aloh:但我也不確定是不是這樣寫就一定對啦!
推 armstrong6v:尊爵 不凡
推 lbebel:氣宇 非凡
推 dwight90488:江　消凡
推 konejr:佳佳好幽默
推 gn2228775:尊爵 榮耀 不凡
→ lbebel:張  克帆
推 ilovecindy:你們好煩= ="
推 lbebel:阿宅沒有potato就如同失去人生的風帆
→ lknuke:推用掉了   樓上太經典
推 lknuke:推用心
推 larry8550:請 莫凡
→ lknuke:最近比較煩
推 y90633:感謝Q_Q
推 jujupp:哈哈~  欣怡耶!
推 lknuke:有下有推   歇歇
推 larry8550:是小朱呢^^