最大值與最小值

在一個有n個元素的，未經排序的陣列中，如果我們要找到最小值，我們可以將一個陣列進行排序，使用merge sort等等方式，接著回傳該陣列的第一個元素，那麼時間複雜度為。

或是我們可以遍歷整個陣列，進行n - 1次比較，並記錄下當前最小的元素，我們就可以找到該陣列中最小的元素。假設有一個陣列A, 長度為A.length = n

MINIMUM(A)
min = A[1]
for i = 2 to A.length
    if min > A[i]
        min = A[i]
return min

在這個情況下，我們只需要線性時間就可以找出最小值，最大值也是同理。

同時找到最大值和最小值

在某一些情況下，我們需要找出個元素構成集合中的最大值和最小值，使用上面漸進式的方法，找出最大值和最小值皆需要次比較，總共需要次比較。

有一個方法可以只進行(表示向上取整數，如)次比較就可以同時找出最大值和最小值。方法為將輸入的陣列元素成雙成對進行處理，先讓一對元素進行比較，把比較小的元素和目前記錄的最小值比較，最大的和目前記錄的最大值進行比較，如此，對每兩個元素只需要3次比較，以下範例

若n為偶數

A = [9,3,1,6,4,5], max=-1,min=999

1. 9和3進行比較，9比-1大，為目前max，3比999小，為目前min，總共進行3次比較
2. 1和6進行比較，6不比9大，max不動，1比3小，故1為目前的min，總共進行3次比較
3. 4和5進行比較，5不比9大，max不動，4不比1小，總共進行3次比較

總計進行9次比較，陣列長度n=6，比較次數3(6/2)=9

---------------------------------------------
若n為奇數

A = [9,3,1,6,4,5,7], max=-1,min=999

1. 先將max和min皆設為9，也就是陣列中第一個元素
2. 3和1進行比較，3比9小，max不動，3比9小，min設為3，總共進行3次比較
3. 6和4進行比較，6比9小，max不動，4比3大，min不動，總共進行3次比較
4. 5和7進行比較，5比9小，max不動，7比3大，min不動，總共進行3次比較

總計進行11次比較，陣列長度為n=7，比較次數3⌈7/3⌉=9

因此，無論陣列長度為何，比較次數皆為

執行時間的期望值為線性時間的選擇演算法

選擇演算法，能夠讓我們知道陣列中第小的數字，時間複雜度為，這是一個使用分治法設計的演算法，概念上和quick sort很像，但不同之處在於quick sort畫將陣列劃分成兩個部分進行處理，而選擇演算法進行劃分，只會對其中一個部分進行處理。

選擇演算法為一種隨機演算法，因為他的部分行為是由隨機數產生器來決定的，以下為RANDOMIZED-SELECT的虛擬碼，他會回傳陣列中第小的元素。

RANDOMIZED-SELECT(A, p, r, i)
    if p == r
         return A[p]
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q]
    else if i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else 
        return RANDOMIZED-SELECT(A, q + 1, r, i - k)
    
RANDOMIZED-PARTITION(A, low ,high)
    i = RANDOM(p, r)
    exchange A[high] with A[i]
    return PARTITION(A, low, high)

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            exchange A[i] with A[j]
    exchangeA[i + 1] with A[high]
    return i + 1

RANDOMIZED-SELECT的情況如下:

• 第1行先檢查陣列中只有一個元素的情況，在這個情況下直接回傳即可
• 第3行呼叫RANDOMIZED-PARTITION把陣列劃分成和兩個區塊，將作為基準點，也就是主元(pivot)
  
• 第4行計算子陣列，分割出的陣列中元素的個數，，指的是加上主元
• 從第5行開始，根據和的關係，存在不同的遞迴情況
• • 如果，表示主元(pivot)即為我們要尋找的元素
• • 如果，表示元素在分割的左手邊，因此改變分割的上界，也就是
• • 如果，也就是剩下的情況，表示元素在分割的右手邊，改變分割的下界，也就是，因為元素皆在右手邊，此時會產生出新的分割，因此我們尋找的目標也要相應跟著做調整，也就是。
    

Example:

給定陣列A[8] = {6,10,13,5,8,3,2,11}，目標為大小排名第7的數字，i = 7

1. 假設我們以A[0]，也就是6作為主元(pivot)，則會產生出以下分割
A'[8] = {2,5,3,6,8,13,10,11}

2.經過分割後，我們可以知道6是排名第4名的元素，=ˊ我們要尋找的元素為第7名的元素，
因此判定元素在右邊的分割，遞迴呼叫後，k = 4，此時我們看到的為右邊的分割
A'[4] = {8,13,10,11}
我們要尋找的數變成在這個子陣列中，排名第3(7 - 4 = 3)的元素，透過這種方式不斷遞迴呼叫，找到我們所求的數字。

實作(找出最大值和最小值)

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

long long randomized_select(long long *,int, int, int);
int randomized_partition(long long*, int, int);
int partition(long long *, int, int);
void swap(long long *, long long *);
int main(void)
{
    long long number = 0;
    long long data[100] = {-1};
    int index = 0;
    while(scanf("%lld", &number) != EOF)
    {
        data[index] = number;
        index = index + 1;
    }
    printf("%lld %lld", randomized_select(data,0,index - 1,index), randomized_select(data,0,index - 1,1));
}

long long randomized_select(long long *A, int p, int r, int i)
{
    if(p == r)
    {
        return A[p];
    }
    int q = randomized_partition(A, p, r);
    int k = q - p + 1;
    if(i == k)
    {
        return A[q];
    }
    else if(i < k)
    {
        return randomized_select(A, p, q - 1, i);
    }
    else
    {
        return randomized_select(A, q + 1, r, i - k);
    }
    
}

int randomized_partition(long long* A, int low, int high)
{
    int i = low + rand() % (high - low + 1);
    swap(&A[i], &A[high]);
    return partition(A, low, high);
}
int partition(long long *a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for(int j = low; j <= high - 1; j++)
    {
        if(a[j] <= pivot)
        {
            i = i + 1;
            swap(&a[i], &a[j]);
        }
    }
    swap(&a[i + 1], &a[high]);
    return i + 1;
}

void swap(long long *a, long long *b)
{
    long long temp = *a;
    *a = *b;
    *b = temp;
}

效率分析

我們假設陣列中的元素皆不相等，假設出現以下幾種情況

• 第一種(好的情況): 產生出的分割為，則遞迴關係式為
  
  使用主定理解遞迴式，，屬於Case 3.
  因此得出
  

也就是在產生出1 : 9分割時，我們可以在線性時間內找到第大的元素

• 第二種(最差情況): 產生出的分割為，則遞迴關係式為
  ，解出來結果為

當產生出最差的分割，也就是其中一個分割沒有任何元素，那時間複雜度為，比先進行排序後再進行元素挑選的還要差

但大多數的時候，我們都會得到幸運的情況，以下證明他的期望執行時間，也就是他的平均情況

我們可能得到的分割，也有可能得到的分割，總共有種劃分的可能，要分析所有可能的劃分，我們可以使用指示器隨機變數(Indicator random variables)進行處理。

假設為演算法在陣列長度為的執行時間，而整個執行時間取決於一個隨機變數，隨機變數決定了我們如何進行分割，隨機變數對於某一個分割的選擇需要是相互獨立的。

令指示器隨機變數，表示任意分割的發生，界於到，則

因此給定一個下標到，不論如何隨機選擇，產生出怎樣的分割，每一種分割對應到的不是，就是。

上面就對應到了所有的分割情況，我們可以使用來標記每一個分割的情況的發生，如果發生就表示，反之為，因此要求出的結果，可以用以下式子進行求解

而我們想知道平均情況，因此使用期望值進行計算

這裡需要計算含有兩個隨機變數函數的期望值，和，兩個隨機變數是相互獨立的，也就是不受彼此影響(這是我們的前提)，是進行分割時產生的隨機數，是在遞迴中產生的隨機數，因此，期望值可以分開處理。

而，表示所有分割情況是否發生，而分割的情況有種，每一種情況皆機率均等的出現，因此，

接著處理函數，可以發現到當和時，函數輸出的結果皆是相同的，因此，我們可以只計算整個式子一半的項數，接著乘上兩倍就可以了。

我們的目標是要得出在平均情況下，這個演算法執行時間仍然為線性時間，觀察我們的式子，如果我們能夠證明的上限是線性時間，那麼證明就完成了。使用代換法讓。

一開始遞迴有兩個假設，我們將運用這三個假設來實現代換法:

1. 假設有一個常數滿足遞迴的初始條件，使得。
2. 假設當小於某一個常數時，存在
3. 假設存在一個常數，使得對所有，滿足

在上面我們得到這樣得結果
，使用代換法進行代換

當足夠大時，的值最多為，也就是
，將提出來，並兩邊乘上
，將兩式同除，得到

因此，，而時，也就是我們歸納假設的第二點，存在。

結論: 當陣列中所有元素皆不相同，平均情況下，我們可以在的情況下找出第大的元素，而最差情況為。

參考資料:Introduction to algorithms 3rd