算法复杂度分析

排序算法复杂度

复杂度.png
希尔排序是 直接插入的优化，直接插入排序在基本有序时，时间复杂度接近O(n)，希尔排序按照由n~1的分组策略，将数据集初期拆解成较小的子集，这时候使用直接插入排序O(n)和O(n^2)的复杂度区别不大，而当子集分组为1时，整个集合已经基本有序，这一趟基本趋向于O(n)，适用于中等规模的数据集

归并排序 采用了分治的方法，自顶向下(二分查找法后做合并)

排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前
稳定性分析

1. 简单规则 时间复杂度

1. 有限次操作 O(1)
2. for循环 O(n)
3. 树的高度 O(log(n))
   BS复杂度是 O(log(n)) 减治法

int BS(int[]arr, int low, inthigh, int target){
         if(low> high) return -1;
         mid= (low+high)/2;
         if(arr[mid]== target) return mid;
         if(arr[mid]> target)
                   return BS(arr, low, mid-1, target);
         else
                   return BS(arr, mid+1, high, target);
}

Heap复杂度是O(lg(n))

2. 组合规则 时间复杂度

1. 冒泡排序
   O(n) * O(n) * O(1) = O(n^2)
2. topK

// 制作堆 O(k)
heap[k] = make_heap(arr[1, k]);
// 循环n次 O（n）
for(i=k+1 to n){
         // 对堆做调整 O(lg(n))
         adjust_heap(heap[k],arr[i]);
}
return heap[k];

O(k) + O(n)*O(lg(k)) = O(n * log(k))

3. 递归求解

1. 先得出常量 f(1) = 1
2. 再求出后续公式，分治 f(n) = 1 + f(n-1)
3. 将f(1) 代入公式可以求出通解

快排复杂度是 O(n*log(n))，但是要使用辅助栈

75 快速排序

void quick_sort(int[]arr, int low, inthigh){
         if (low>=high) return;
         // for找出中间值，O(logn)
         int i = partition(arr, low, high);
         // f(n/2) - 分治左
         quick_sort(arr, low, i-1);
         // f(n/2) - 分治右
         quick_sort(arr, i+1, high);
}
private int partition(int[] nums, int lo, int hi) {
        int p=nums[lo];
        while(lo<hi) {
            while(lo<hi && p<=nums[hi]) hi--;
            nums[lo]=nums[hi];
            while(lo<hi && p>=nums[lo]) lo++;
            nums[hi]=nums[lo];
        }
        nums[lo]=p;
        return lo;
    }

4. 分治与减治

• 分治法，每个分支都要递归，例如：快速排序 O(n*log(n))
• 减治法，只要递归一个分支，例如：二分查找 O(log(n))，随机选择 O(n)
• O(分治法) > O(减治法)

随机选择/快速选择算法减治法

int RS(arr, low, high, k){
  if(low== high) return arr[low];
  i= partition(arr, low, high);
  temp= i-low; //数组前半部分元素个数
  if(temp>=k)
      return RS(arr, low, i-1, k); //求前半部分第k大
  else
      return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}

5. 斐波那契数列

1. 从大到小递归，尽可能不要使用递归，会有大量栈，容易跑死机
2. 正推法，使用 f(n) = f(n-1) + f(n-2) 从小到大累加 O(n)

6. 正整数的二进制表示包含多少个1

1. 根据整数的位数m，每次n>>=1，n&1==1说明存在一个1，O(m)
2. n&(n-1)这个操作，可以起到消除最后一个1的功效， O(m/2)

while(n){
   result++;
   n&=(n-1);
}

6. 堆

大顶堆 子节点都小于父节点
小顶堆子节点都大于父节点

7. 计数排序

当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法
当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法

8. 桶排序 Bucket Sort

先将数据放置在对应的桶中（桶内暂时是无序），在排序的时候，对桶内数据做插入排序
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度

9. 基数排序 Radix Sort

从个位开始，先排序放置在对应的额外空间，再按顺序放置回原数组，再从十位依次类推
基数排序的空间复杂度为O(d*2n)d较小，约等于 O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右

10. 红黑树

红黑树大多数的操作所需要的时间都是对数级别的 O(logn)
平衡树的插入和删除的时间复杂度