rabbit82047

THANK YOU!! 我走去問人, 人地仲話個SIZE 冇可能係12..
但係其實第28行句 size =4 *size;
有咩作用?? ...
刀仔刀刀神 發表於 2013-10-17 08:31

expand method 做既野就係
將 element 既 accessible size * 4
原有既 member value 按比例 spread  開
中間多出黎既 member 用 pass in value 填充
size = 4 * size 就係要將 accessible size 放大

正常 expand array 仲要 check capacity 夠唔夠,
不過一條練習題唔講咁多啦

刀仔刀刀神

多謝大佬既解答, 幫左我好多

另外小弟唔多明點計time complexity,
如果以呢條為例,
應該點計?? (big-O果隻)

rabbit82047

回復 12# 刀仔刀刀神

Time complexity 你 google 可能好d, 做野之後都唔會去計, 佢話係 O(n) 就 O(n), O(log n) 就 O(log n)

以 expand 黎講

1. for (int i = n; i >= 0; i--) {
   
2.         element[4 * i + 3] = a; // run n times
   
3.         element[4 * i + 2] = a; // run n times
   
4.         element[4 * i + 1] = a; // run n times
   
5.         element[4 * i] = element[i]; // run n times
   
6. }
   
7. size = 4 * size; // run once

複製代碼

結果 total 有 4n+1 個 operation, time complexity 就係 O(n) linear time

O(n^2) example - (n^2 - n) / 2

1. for (int i = 0; i < N; i++) {
   
2.         for (int j = 0; j < i; j++) {
   
3.                 statements
   
4.         }
   
5. }

複製代碼

O(log n) example - 2^x = n = log2(2^x) = log2(n)

1. for (int i = 1; i < N; i *= 2) {
   
2.         statements
   
3. }

複製代碼

如果有 if else 仲要計 worst/best case, 係咁多, 其他要重新學返

刀仔刀刀神

回復  刀仔刀刀神

Time complexity 你 google 可能好d, 做野之後都唔會去計, 佢話係 O(n) 就 O(n), O(log ...
rabbit82047 發表於 2013-10-17 19:49

   要計真係唔好講笑....
睇到我呢...

師兄熟唔熟bubble sort ?? 我又遇到問題

tuyylihk

而家呢度有幾條友剩識係度用d同程式完全無關既野係度串人
但實情完全無料,唔識答野
樓主可以唔駛理

練習題通常係比你熟悉個flow同幫你做解釋多於實際用途
呢條例題係比你容易理解,實際做冇乜理由咁搞法

sorting網上應該好多例子同埋圖解,尤其bubble sort係好基本既排序法...
你有咩問題?

tuyylihk

我唔係喎CHING 兄， 我真係去IBM SEARCH 咗野來學喎。
Flower 發表於 2013-10-18 10:17

妖,明知唔係講緊你咪插埋黎啦

rabbit82047

回復 14# 刀仔刀刀神


bubble sort algorithm 上網 search 就有好多 implementation 同教學

有咩唔清楚, 係度 post 出黎, 自然有 ching 答你

杜龍

其實化化哥可能同小弟一樣, 上左做SA之後無晒時間寫曲. 搞到甩甩地. 吹水多過DUP石仔.