上海 培训网站建设合肥百度关键词推广

使用：master公式计算。
当满足T (n) = a * T(n/b) + O(n^d) 时。其中T(n)为样本量的时间复杂度，a为子过程发生多少次，T(n/b)子过程的样本量的时间复杂度，O(n ^d)为除了子过程以外，其他操作所需的时间复杂度。
1.log(b,a) < d 时，时间复杂度为O(n^d) 。
2.log(b,a) = d 时，时间复杂度为O(n^d * log n)。
3.log(b,a) > d 时，时间复杂度为O(n *l og(b,a) )。

以归并排序为例:

//归并l...r的元素，l为左边界，m为划分点，r为右边界template<typename T>void mymerge(T* arr, int l, int m, int r)           {if (arr == nullptr || l < 0 || m < 0 || r < 0)return;T * help(new T[r - l + 1]);     //辅助数组int i = 0;int index1 = l;                int index2 = m + 1;//归并划分的两部分，第一部分是下标 index1<=m 的，另一部分是下标 m+1<= index2 <=rwhile (index1 <= m && index2 <= r) {help[i++] = arr[index1] < arr[index2] ? arr[index1++] : arr[index2++];        }//两部分有且仅有一部分没有越界（下面的while只有一个会执行）while (index1 <= m) {help[i++] = arr[index1++];}while (index2 <= r) {help[i++] = arr[index2++];}//拷贝原数组for (int j = 0; j < i; j++) arr[l + j] = help[j];delete help;	}template<typename T>void mergeSort(T arr[], int left, int right) {if (arr == nullptr || left >= right)return;int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);mymerge(arr, left, mid, right);}template<typename T>void mergeSort(T arr[], int size){mergeSort(arr, 0, size - 1);}

分析：归并排序时，子过程调用了2次(mergeSort),所以 a = 2; 排序过程中使用递归将样本量分为以mid为界的两部分，所以b=2，子过程样本量为 n/2;在归并时需要一个辅助数组来存储排序的数据，最后再将辅助数组的数据拷贝到源数组，操作指令为n的常数倍，所以d = 1;因此 log(b,a) = log(2,2)= 1 = d；所以归并排序的时间复杂度T(n) =O (n^d * log n) = O(n * log n) 。