演算法上課筆記(第二周)

後來想想每周有兩天上演算法
每次上完課就做筆記的話好像有點太繁瑣了
其實是我自己太懶
所以就用每周的方式來做筆記整理
我想這樣到時候我也比較好閱讀吧?

不多說廢話了 以下開始正題
=================================================================

這次上課有講到4種演算法

• Straight insertion sort (插入排序
• Binary search (二元搜尋
• Straight selection sort (選擇排序
• Quick sort (快速排序

=================================================================


Straight insertion sort

從字面上翻譯 就是 直接 插入 排序 (有點糟糕貌XD

插入排序 就如同字面一般，運用插入的先來後到順序，新進來的數字若是比自己小就將它放到陣列較前面的位置，反之，較大的話，就放在陣列的後方。

舉例來說

round 0 | ７  ５  １  ４  ３  ２  ６  來做排序　順序會如下圖
round 1 | ７                        從左第一個數開始插入
round 2 | ５  ７                     類推之 插入5 但5比7小故 擺在前面
round 3 | １  ５  ７                  插入1
round 4 | １  ４  ５  ７               插入4
round 5 | １  ３  ４  ５  ７           插入3
round 6 | １  ２  ３  ４  ５  ７        插入2
round 7 | １  ２  ３  ４  ５  ６  ７    插入6

後來找到wiki上有比較明顯的動畫

下面是課本上附錄的虛擬碼

input： X1,X2,....Xn
output：
For j := 2 to n do
Begin
  i := j - 1
  x := Xj
  While x < Xi and i > 0 do
  Begin
    Xi + 1 := Xi
    i :=  i - 1
  End
  Xi+1 := x

End

code 的部分我就不多做解釋了
接著要來分析三種情況

Best case （最好情況），Worst case（最糟情況）  ，Average case（平均情況）


但得先說說 這演算法到底做了多少事情


首先，從上面的程式碼跟動畫可以知道一件事情
無論如何，每次排序都會 抓起 以及 放下 一次，就算該數字不用移動
也會被抓起來再放回原位。

再來，要確定會有幾回合，以Ｎ個數字來作例子的話，總共會做Ｎ-１個回合才會結束。

最後只要確定每回合內 需要做幾次的排序 就可算出每種情況的解

∑( i from 2 to N){2(抓+放)+di(sort的次數)} 

上面就是我們得出來的通式 (在每回合做了多少動作

如此這般，就可以來想想Best case 是怎麼回事！

在這個情況之下用到的動作數會是最少的，可想而知，
排序最少的情況就是～～～～　一開始就排好了！！

所以每次每個元素只會做 抓 跟 放 兩個動作(無須sort)共做了n-1次

得到了Best case的解為 2(n-1) →bigO(n)。
-----------------------------------------------------------------
接著要討論Worst case 也就是最糟的情況，聽起來很難耶！不過仔細想想其實很簡單
在Best case中 的數列 是 由小到大 依序排列的，如此一來不用對每個元素sort，反向思考一下
那不就是要每個數字都有sort，而且次數越大越好，繼續想下去.....那不就是每個元素離自己sort好得位置越遠，就會作越多次sort；那麼結論就已呼之欲出 -- 完全反著排！

在這裡我們先不考慮抓與放的部份 之後在加算回來，先算出sort的部份，這樣會簡單很多。

自己試著用簡單的例子就會發現其中的規律（ex: 5 4 3 2 1)
d1 = 1, d2 = 2, d3 = 3 ..... dn = n-1
接著運用小學數學 將其總和算出 為 n(n-1)/2。
所以再加上 抓放次數　2(n-1)  就可以得到 2(n-1) + n(n-1)/2 ，但這樣很難取bigO，所以在簡化一下，得到 (n-1)(n+4)/2  → bigO(n^2) 。
-----------------------------------------------------------------
講到這裡，接著就是最麻煩的Average case，既然叫做平均，當然亂想就會想到機率統計，
在這排序法中 抓與放 都是固定的直 ，那能下手的只剩sort的部分了，所以該做的就是取出sort的期望值再做加總。
說起來很容易啊～ 但想起來真的很麻煩，誰知道那天殺的期望值怎麼算.....
我就回去看原本的虛擬碼，就發現每個元素做排序時只會跟自己左邊的做交換看來就可以推出個
道理：第i個元素 可能的sort 次數是 0~i-1次(i>=2,共i種)，所以每種可能有1/i的機率
期望值：0~i-1 * 1/i
這時候再把抓放的 2 加上去

式子就會變成這樣 2/i + 3/i +...+ (i+1)/i  =  (i+3)/2

再帶入最前面的通式 可以得到

∑( i from 2 to N) {(i+3)/2}

再簡化下 可得 (n-1)(n+8)/4 = bigO(n^2)
=================================================================

Binary search
二元搜尋

也就是二分逼近法

請注意
他只能用在
排序好
排序好
排序好
的數列之中。
首先，將數列從中間切分，如果搜尋的目標比最中間的數字大的話
就往切剩下的右邊數列裡找，反過來說比較小的話就往左邊找，作個幾輪之後就可以之道有沒有找到。

接下來直接就把虛擬碼用上來吧!

input: a1,a2,.....,an, n>0 排序過 由小到大的數列; X 為要找的數字

output: 
  i := 1(頭) 
  m := n(尾)
while i <= m do
begin
  j:= floor((i+m)/2) 取與結果相近的最小整數
  
  If X = aj 找到了,停下來 直接輸出j下面程式碼全部跳過
  If X < aj then m:=j-1 繼續往左半邊尋找
  else i := j+1 大於的情況下往右半邊找
End

j:=0

若j!=0 那就是有找到,反之就是沒找到

-----------------------------------------------------------------
接下來也是要判斷 那三種情況
為了方便好算，所以要先求出通式！
首先觀察上面的演算法可以發現到一件事.....搜尋次數
因為每次搜尋都是砍半，所以用到神奇的高中數學吧！
取log!!!

假設一下 n = 2^k - 1 
來猜k = ? 
  k = log(底為2) n     <---很明顯有錯阿ˊ_>ˋ
    = floor(log(底為2) n) <--- 這個稍微好一點了 但是奇數情況下 次數有小數點?
    = floor(log(底為2) n)+1 <---這麼就求出來
k其實就是最大搜尋次數


接著下來就算好解了

-----------------------------------------------------------------
Beset case:
這似乎是膝蓋一般簡單的事情?
總之一搜尋就找到了所以
當然是 BigO(1)
-----------------------------------------------------------------
Wrost case:
找東西最糟糕的是什麼？找不到嘛~(廢話XD

所以說就是找最大次數 套上面的結果 就是 floor(log(底為2) n)+1
結果當然就是BigO(log n)   (樂勝XD
-----------------------------------------------------------------
Average case:
又遇到最變態的平均了~

不過也還好，只要整理出該算什麼東西就好

1. 找的到數字有幾個?
2. 找不到的數字有幾種?
3. 每個數字有每個數字的位置

1 與 2看起來就是會有一些相關性
所以先來處理這兩件事情
用舉例最快速

5 6 7 8 9 <----這串數列有5個數字 ，所以能找到5個數子
_5_ 6_ 7_ 8_ 9_ <----數字之間的空位有6個 所以有6種數字會找不到
(比5小，5.6之間 ，6.7之間 ，7，8之間 ，8.9之間 ， 比9大 )

類推時間~
所以有n個數字 可以找到n個數字
並且有 n+1個空格 所以有 n+1個數字找不到



3考慮到每個數字的位置
有些數字可能找一次就找到了 有些則可能要找很多次~
 再用剛才的例子
 56789
 32123 (找到的次數

再來個例子
3 4 5 6 7 8 9
3 2 3 1 3 2 3 (找到的次數

1----1 = 2^0
2----2 = 2^1
3----4 = 2^2

這是一個規律

∑(i from 1 to k)2^i-1 搜尋次數是由內往外以2^i-1遞增的
這裡的k是指上面算到的 最多k次

稍微把上面的東西整合一下
∑(i from 1 to k)2^(i-1) + k(n+1) <-包含所有找的到的以及找不到的數字
A(n) = {∑(i from 1 to k)i*2^(i-1) + k(n+1)}/(2n+1) <- 再將有找到的部分乘上次數 最後除所有可能性(2n+1) 就可以得到期望值

礙於篇幅 我就跳過解開這個式子的步驟了， 最後可以得到

((k-1)*2^k+1+k2^k)/(2n+1)
這時候假設 n很大的情況
n = 2^k-1 進入代換，並且省略分子的+1
->((k-1)*2^k+k2^k)/(2^(k+1)
->(k-1)/2 + k/2
= k - 1/2

到此A(n)小於k 又因為 k = BigO(log n) 所以得到的結果就是 A(n)= BigO(log n) =================================================================

Straight selection sort
前面打這麼多有點小累....所以偷懶下 以下就是選擇排序..結束

選擇排序用講得實在是很困難....
我把上面的動畫轉換成個round來看好了
         8 5 2 6 9 3 1 4 0 7

round 1 |8 5 2 6 9 3 1 4 0 7
round 2 |0 5 2 6 9 3 1 4 8 7
round 3 |0 1 2 6 9 3 5 4 8 7
round 4 |0 1 2 6 9 3 5 4 8 7
round 5 |0 1 2 3 9 6 5 4 8 7
round 6 |0 1 2 3 4 6 5 9 8 7
round 7 |0 1 2 3 4 5 6 9 8 7
round 8 |0 1 2 3 4 5 6 9 8 7
round 9 |0 1 2 3 4 5 6 7 8 9
round 10|0 1 2 3 4 5 6 7 8 9



這樣看來清楚多了，簡單來說就是每次找出「未排序的子數列」中最小的數字與再與該數列的最前面元素作交換。

input:A1,A2,A3,...,An.
output:
For j:=1 to n-1 do
 Begin
  f :=j
  For k := j+1 to n do
    If Ak < Af then f := k
  Aj<->Af //Aj,Af 互換 //
 End

------------------------------------------------------------------------------------------------------------
接著又要來求三種case ，不過要先討論通式。

設在有n個「未排序的元素」下的每個round平均會做 Xn個動作；並立通式為A(n);

觀察上面的圖片可以了解到，每個round之後 會固定1個元素，剩下的就是「未排序的子數列」，這看起來就很像是個遞迴的感覺，每次都做一樣的事情，但數列有作收斂。

所以拿出離散數學中的遞迴關係式可以的到下面的結果

A(n) = Xn + A(n-1)

看這式子裡只有Xn我們可以再做變化，所以來推想一下Xn，我剛剛定義下的就是平均的動作
那這不就是期望值嗎？



令Pn(k) 是 有n個元素下 移動k次的機率
那麼 k Pn(k) 就是他的期望值了
尤上面的圖片可以知道 一個數列最多就移動n-1次
所以推的下面的式子

Xn=∑(k from 0 to n-1) {k Pn(k) }

-----------------------------------------------------------------
best case:
已經排好了所以就不排了
那當然是big-O(1)
-----------------------------------------------------------------
worst case:
在完全相反的數列 對於selection sort　每次都要從頭找到尾
過程很簡單有空我在補
最後可以推測出為bigO(n^2) 
-----------------------------------------------------------------
average case:
稍微看了下課本跟筆記 有整整兩三面的數學歸納法....
我絕望了 故我只提供結果 bigO(nlogn)
=================================================================

Quick sort
晚點補

qsort 簡單而言，就是二分法,有n個元素將頭當作基準，比較小的就放左邊，比較大的則放右邊，整理完之後 可有左（小）右（大）的兩個子堆，兩個子堆在分別取頭當作基準，
作大小分類，之後又會各出現兩個子堆（共計四堆），以此類推。

p.s.上述情況是比較理想的狀態，不一定每次都可以分到兩堆

虛擬碼



input Af, Af+1, ... , Al

Quick sort(f,l)

If f>=l then Return

X:=Af

i:=f

j:=l

While i < j do

Begin

  While Aj >= X and j >= f+1 do

    j:=j-1

 

  While Ai <= X and i <= l do

    i:=i+1

  if i<j then Ai<->Aj //Afi互換Aj//

End

Af<->Aj//Af互換Aj//

Quicksort(f,j-1)

Quicksort(j+1,l)

-----------------------------------------------------------------
好了來談談 那三個case吧......

因為這個排序法比較特殊所以不先推導通式
但要先釐清這個排序法

拆分拆分再拆分！

要考慮 拆分了幾次 跟 每次排序次數
這演算法的總次數 就是 拆分了幾次 * 每次排序次數
-----------------------------------------------------------------
best case:
在最好的情況之下，n個元素，每次都可以拆成數量均等（或差一）的兩堆
如此一來可以知道拆分的次數就會是　log(底2)n ，接著考慮每次排序次數 ，
第一次排序 1*n
第二次排序 2*((n-1)/2) <------左右兩堆，(n-1)是因為第一次已經固定一個數字了
第三次排序 4*((n-2)/4) <------第二次的兩堆 再做拆分共四堆，(n-2)理由同上
......類推
不過 (n-？) 因為我們是在算bigO，所以其實可以忽略不看
那就簡單許多
第一次排序 1*n = n
第二次排序 2*(n/2) = n
第三次排序 4*(n/4) = n
每次都是n ，總共做log(底2)n次
得到結果就是 bigO(n log n)
-----------------------------------------------------------------
worst case:
想想qsort的根本，就是拆分，再將兩堆作排序，那最糟的情況就是---只能分成一堆，這樣完全就變成selection sort了～
比如說 1 2 3 4 5 6 7 8 9
或是 9 8 7 6 5 4 3 2 1
就是一個 排序好 或是 完全反著排好 的 數列
從selection的經驗可想而知
總共會有n次的拆分
每次都是把剩下的數作排序
所以結果就是 n+(n-1)+(n-2)+...+1 = n(n+1)/2
bigO(n^2)
-----------------------------------------------------------------
average case:
終於到了最後一個了.....
qsort的拆分 我們假定他會作T(n)次 (T()是個函數,n是代表數列長度)
下次又會在拆乘兩堆作同樣的事情
.....
.......這根本就遞迴啦～！

T(n) = T(s) + T(n-s) <---拆成兩堆了~

T(n) = Ave( T(s) + T(n-s) )<----因為兩堆可能有各種情況所以還要再取平均

T(n) = Ave( T(s) + T(n-s) )+ cn <----cn 就是該次的排序+拆分

中間有很多種算法，但中心思想不外乎使用遞迴關係式，這邊就先不寫了。
其實不用算也猜得到答案式bigO(n^2)，為什麼呢？　因為這就跟selection sort
的worst長的很像
=================================================================

後記：
終於寫完第二周了....進度嚴重落後阿～～～

＃圖片轉載自維基百科