補充數值分析Q4

看板YZU_CN99A作者aloh (aloh)時間15年前 (2009/01/08 23:58)推噓11(11推 0噓 1→)

留言12則, 9人參與討論串1/1

※ 引述《y90633》之銘言： : Q1.VP diagrams and Linked List : 1.如何定義linked list 答題要寫程式碼 : Ans. struct LLNode{ : char key; : struct LLNode *next; : }; : 2.寫一個副程式去處理整串linked list裡的資料 (答題要寫程式碼) : Ans. 自己參考課本p.82 : 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.做法就跟p272的那個一樣，實驗課做的是實驗那張10.4的那個 : ====================================================================== : 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. 有課本的請看課本p276 第四題對照p415的解答應該可以看出所以然總之就是先找中間把不需要的那半就不理他像這題要找X 所以左半邊就不管了之後再找右半邊的中間依此類推直到找到為止!!! : 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 來自: 140.138.247.59 (01/08 23:59)

→

shuding001

01/08 23:59, , 1^F

01/08 23:59, 1^F

※ 編輯: aloh 來自: 140.138.247.59 (01/09 00:01)

推

shuding001

01/09 00:01, , 2^F

01/09 00:01, 2^F

推

Slash520

01/09 00:02, , 3^F