基本原则

1、如果运行时间是常数量级，用常数1表示；

2、只保留时间函数中的最高阶项；

3、如果最高阶项存在，则省去最高阶项前面的系数。

$O (l o g_{2} N)$ 的判断

“运行时间中的对数”的一般法则规定：

如果一个算法用常数时间(O(1)将问题的大小削减为其一部分（通常是1/2），那么该算法就是 O(log N)。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是 O(N) 。

递归问题的判断

斐波那契数列

long aFunc(int n)
{
  if (n<=1) return 1;
  else return aFunc(n-1)+aFunc(n-2));

显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列

这里，给定规模 n，计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

                 fib(5)   
             /             \     
       fib(4)                fib(3)   
     /      \                /     \
 fib(3)      fib(2)         fib(2)    fib(1)
/     \        /    \       /    \

也就是说，计算了 $2^{n}$ 个fib(1)。

简单规则

1.只关注循环执行次数最多的一段代码

2.加法法则：总复杂度是量级最大的那段代码的复杂度

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n) = T1(n)+T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

4.不考虑非浮点数计算的元素大小比较语句

一般循环的判断，计数，以及if 的比较操作，不计算在内

十大排序算法的最坏时间复杂度分析

参考

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

https://www.inf.hs-flensburg.de/lang/algorithmen/sortieren/index.htm

冒泡排序

#include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1])
                                swap(arr[j], arr[j + 1]);
}
int main() {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;
        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (float) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ' '<<endl;
        return 0;
}

找出算法运行最多的代码swap(arr[j], arr[j + 1]);运行了 $[(n-1)+...+1]=\frac {n*(n-1)} 2$ 次。则时间复杂度为 $O (n^{2})$

选择排序

template<typename T> //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能
void selection_sort(std::vector<T>& arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
                int min = i;
                for (int j = i + 1; j < arr.size(); j++)
                        if (arr[j] < arr[min])
                                min = j;
                std::swap(arr[i], arr[min]);
        }
}

找出算法运行最多的代码std::swap(arr[i], arr[min]);运行了 $[(n-1)+...+1]=\frac {n*(n-1)} 2$ 次。则时间复杂度为 $O (n^{2})$

插入排序

void insertion_sort(int arr[],int len){
        for(int i=1;i<len;i++){
                int key=arr[i];
                int j=i-1;
                while((j>=0) && (key<arr[j])){
                        arr[j+1]=arr[j];
                        j--;
                }
                arr[j+1]=key;
        }
}

找出算法运行最多的代码arr[j+1]=arr[j];运行了 $[1+...+(n-1)]=\frac {n*(n-1)} 2$ 次。则时间复杂度为 $O (n^{2})$

希尔排序

希尔排序是插入排序的改进，基于如果插入排序基本有序的情况下，排序速度会变得很快的原理，根据某个增量序列 $\{t_1,t_2 ...t_k...t_m\}$ 进行迭代，第一次迭代将序列分为 $\frac n {t_m}$ 个部分进行排序，在迭代在至 $t_{1} = 1$ ，此时由于数据基本有序，所以使用插入排序会使得排序速度很快。

希尔排序的最坏时间复杂度和增量序列的设置有关，如果是 $\{1,2,4,...2^k\}$ 则为 $O (n^{2})$ ，如果是 $\{1,3,7,...,x^k-1\}$ 则为 $O(n^{1.5})$ ,如果是Sedgewick提出的 {1, 5, 19, 41, 109,...}则为 $O(n^{1.3})$ . 希尔排序不稳定，适用于5000左右的小数据排序，此外在数据存在一定有序性的情况下，排序会更快。

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}

归并排序

递归的归并排序可以得到递归的二叉树,层数是 $l o g_{2} n$ ,每层有 $\frac n {2^k}$ 个单元，第 $l o g_{2} n$ 层每个单元进行1次基本运算，第 $l o g_{2} n - 1$ 层每个单元进行(4-2)次基本运算，第1层进行(n-2)次基本运算。因此总共进行 $(\frac n 2 + \frac {2n} 4 +\frac{6n} 8 +...+\frac{n(n-2)} n)$ 次运算，共有 $l o g_{2} n$ 个加数，因此最坏和最优时间复杂度都为 $O (n l o g_{2} n)$

//递归版
void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

快速排序

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

//严蔚敏《数据结构》标准分割函数
 Paritition1(int A[], int low, int high) {
   int pivot = A[low];
   while (low < high) {
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   A[low] = pivot;
   return low;
 }

 void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }

时间复杂度分析方法