Harmonisation Algorithme

Time complexity：
算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。
       一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

主定理的应用

求解递推方程，       T(n)= aT(n/b) + f(n)

a:规约后子问题的个数 a >= 1

n/b:归约后子问题规模 b > 1

f(n): 归约后子问题工作量 f(n) 为函数

主定理推导

这里表示的递归，是指：将一个n规模的问题，分解为a个子问题，其中每个子问题的规模为n/b。在读这一章的时候，我其实不太懂这个主定理的意思。主要是不懂为什么要比较f(n)和nlogba。今天又看了一下这一章和大概的证明过程，似乎明白了一些。

先说nlogba这个多项式的由来。使用递归树来计算T(n)的时候，Θ(nlogba)是递归树所有叶子节点的和，也就是整个递归过程的非递归代价。在T(n)=aT(n/b)+f(n)中，f(n)是每次递归都要执行的部分的代价，即递归代价。这两者的代价都是随着递归的迭代而增长的。比较f(n)和nlogba其实就是判断当n足够大时，影响增长趋势的是谁。

为了表示这种区别，这里的比较大小，使用的其实是“多项式大于/小于”。我们说f(n)多项式大于g(n)，即f(n)/g(n)的结果为n的多项式。这样的意义在于当n足够大时，对于f(n)来说，g(n)的增长可以忽略不计。也只有在这种情况下，才忽略g(n)的影响。在主定理中，f(n)和g(n)即分别是f(n)和nlogba。在主定理中，通过引入ε来表示多项式大于/小于。

现在分别看一下这三个case。

1. f(n)=O(nlogba–ε) 的情况下，f(n)明显多项式小于nlogba，所以这个时候我们可以认为代价主要集中在递归部分。即T(n)=Θ(nlogba);
2. 这里对于大小的判断是通过 logkba系数来表示的。在《算法导论》的书中直接使用了θ(nlogba)，然而在MIT的公开课中，却增加了logkba系数。书中的形式应该只是k=0的特殊情况。
3. 第三条的重点有两个，第一还是多项式大小的判断，这里还是使用ε来表示的。根据下界函数的定义，可以判断f(n)是多项式大于nlogba的。同时还要注意第二点，这个条件下出现了新的常数c<1 color="rgba(0, 0, 0, 0)" font="">af(n/b)⩽cf(n) 的含义在于，当n足够大的时候，对于每次递归分解，分解之后的子问题的代价总和，是小于分解前的代价的。为什么case 1没有这个限制？因为case 1中不关心递归代价。于是这个时候我们可以忽略非递归代价的增长，将T(n)限定在Θ(f(n))中。

以下是算法

各种算法的最坏情况和平均情况下的复杂度：
1.Insertion sort O(n) O(n²)
2.Bubble sort O(n²) O(n²)
3.Quick sort O(n²) O(n*logn)
4.Heap sort O(n*logn) O(n*logn)
5.Merge sort O(n*logn) O(n*logn) 

1.Insertion sort:

伪码：

Insertion_sort(A,begin,end)

  for begin+1 to end do:

     key <- a="" begin="" font="">

     while (A[begin] > key && begin >= 0) do:

         key <- a="" begin="" font="" nbsp="">

         begin <- -="" 1="" begin="" font="">

    A[begin + 1] <- font="" key="">

end

伪码：

Bubble_sort(A,begin, end)

    for begin+1 to end do:

     while (A[begin] > A[begin + 1]) do:

     swap(A[begin], A[begin + 1]);

     begin = begin + 1;

end

伪码：

Merge_sort(A,begin,end)

    if(begin < end)

       then mid = (begin+end)/2;

    Merge_sort(A, begin, mid);

    Merge_sort(A,mid + 1, begin);

    Merge(A,begin, mid, end);