Day-17 中位数与顺序统计

最大值与最小值

在一个有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