小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

算法学习(2):分治法(上)

2018年12月7日 969点热度 0人点赞 0条评论

二分法

1.算法设计

用一维数组S[]存储该有序序列,设变量low和high表示查找范围的下界和上界,middle表示查找范围的中间位置,x为特定的查找元素。

(1)初始化。令low=0,high=n-1。

(2)middle=(high-low)/2。

(3)判断low<=high是否成立,若成立,到第4步,否则算法结束。

(4)判断S[middle]与x的关系:若S[middle]>x,则x位于low~middle之间,令high=middle-1,;若S[middle]<x,则x位于middle~high之间,令low=middle+1;转第2步。若S[middle]==x,则搜索成功,退出。

2.图解

数据结构学习笔记已有整理,在此省略图解。

3.完整代码

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int M = 10000;

int x, n, i;

int s[M];

int BinarySearch(int n, int s[], int x)

{

    int low = 0;

    int high = n - 1;

    while (low <= high)

    {

        int middle = low +(high - low) / 2;

        if (x < s[middle])

            high = middle - 1;

        else if (x > s[middle])

            low = middle + 1;

        else

            return middle;

    }

    return -1;

}



int main()

{

    cout << "Please enter the number of these elements: ";

    cin >> n;

    cout << "Please enter the element: " << endl;

    for (i = 0; i < n; i++)

    {

        cout << "Element " << i+1 << ": ";

        cin >> s[i];

    }

    sort(s, s + n);

    cout << "After sorted: " << endl;

    for (i = 0; i < n; i++)

        cout << s[i] << " ";

    cout << endl;

    cout << "Please enter the element that you want to find: " << endl;

    cin >> x;

    int ans = BinarySearch(n, s, x);

    if (ans == -1)

        cout << "Sorry, we can not find it.\n";

    else

        cout << "The answer is " << ans+1 << ".\n";



    system("pause");

    return 0;

}

 

排序复杂度为O(nlogn),二分查找复杂度为O(logn)。

递归版:

int BinarySearch(int n, int s[], int x,int low, int high)

{

    if (low > high)

        return -1;

    int middle = (low + high) / 2;

    if (x == s[middle])

        return middle;

    else if (x > s[middle])

        return BinarySearch(n, s, x, middle + 1, high);

    else

        return BinarySearch(n, s, x, low, middle - 1);

}

 

此方法二分查找复杂度仍旧是O(logn)。

合并排序

1.算法原理

将一大组数据,采用分治策略,分成很多个小问题。由于给定的是一个无序的大序列,可以把待排序列分解成两个规模大致相等的子序列,如果排序还是比较困难,则将子序列继续分解成两个规模大致相等的子序列,直到每个子序列的元素个数为1。然后进行合并,合并成完整的有序序列。

2.算法设计

(1)分解:将待排序列分解成大小相等的两个子序列;

(2)治理:将两个子序列进行合并排序;

(3)合并:将排好序的有序子序列进行合并,得到最终的序列。

合并的策略:采用i,j,k三个标志位,以及一个名为B的辅助数组。i,j分别位于A数组的0和mid+1位置,k指向B的起始位。由于A数组的0~mid,mid+1~end均为已经排好序的子序列,所以开始比较A[i]和A[j]。若A[i]>A[j],则将A[j]的数字存入B[k],然后j++,k++;若A[i]<A[j],则将A[i]的数字存入B[k],然后i++,k++;若此时某个数组已经比较完,则直接将另一个数组依序存入B,然后把B重新一一赋值给A,完成对A的排序。

3.完整代码

void Merge(int A[], int low, int mid, int high)

{

    int *B = new int[high - low + 1];

    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high)

    {

        if (A[i] >= A[j])

            B[k++] = A[j++];

        else

            B[k++] = A[i++];

    }

    while (i <= mid)

        B[k++] = A[i++];//把剩下的元素复制到B中

    while (j <= high)

        B[k++] = A[j++];//把剩下的元素复制到B中

    for (i = low,k=0; i <= high; i++)

    {

        A[i] = B[k++];

    }

    delete[] B;

}

void MergeSort(int A[], int low, int high)

{

    if (low < high)

    {

        int mid = (low + high) / 2;//取中间点

        MergeSort(A, low, mid);//对A[low:mid]中的元素进行合并排序

        MergeSort(A, mid + 1, high);//对A[mid+1:high]中的元素进行合并排序

        Merge(A, low, mid, high);//合并

    }

}

 

4.复杂度分析

时间复杂度:

(1)分解:O(1);

(2)治理:2T(n/2);

(3)合并:O(n)。

总的来说,T(n)=O(nlogn)。

空间复杂度:O(logn)。

快速排序

1.算法原理

通过一组排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有数据都要笑,然后按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此使所有数据变成有序序列。

快速排序是不稳定的算法!

2.算法设计

(1)分解:先从数列中取出一个元素作为基准元素,以基准元素为准,将问题分解为两个子序列,使小于等于基准元素的子序列在左侧,大于基准元素的子序列在右侧。

(2)治理:对两个子序列进行快速排序。

(3)合并:将排好序的两个子序列合并在一起,得到原问题的解。由于排序是原地进行的,所以在排好序后,合并步骤无需做什么,序列就已经排好序了。

一般来说,基准元素的选取有以下几种方法:

(1)取第一个元素;

(2)取最后一个元素;

(3)取中间位置的元素;

(4)取第一个、最后一个、中间位置元素三者的中位数;

(5)去第一个和最后一个之间位置的随机数k(low<=k<=high),选取R[k]做基准元素。

这个算法的难点在于“划分”,也就是分解这个步骤。

我们编写划分函数对原序列进行分解,分解为两个子序列,以基准元素pivot为界,左侧子序列都比pivot小,右侧子序列逗比pivot大。先从右向左扫描,找到小于等于pivot的数后,执行R[i]与R[j]的交换,然后进行i++,也就是从左向右扫描,找到比基准元素大的数,执行R[i]与R[j]的交换,然后进行j++……如此交替进行,直到i=j的时候停止。

3.完整代码

int Partition(int r[], int low, int high)

{

    int i = low, j = high;

    int pivot = r[low];

    while (i < j)

    {

        //当r[j]>pivot的时候,就继续由右往左寻找小于的元素

        while (i<j && r[j]>pivot)

            j--;

        //跳出while循环说明找到了,再判断下i<j,然后交换i和j的元素,然后i++,再开始从左向右寻找r[i]>pivot的元素

        if (i<j)

            swap(r[i++], r[j]);

        //当r[i]<pivot的时候,就继续加i,直到找到r[i]>pivot的时候,跳出wile循环

        while (i < j && r[i] <= pivot)

            i++;

        //跳出while循环说明找到了,再判断下i<j,然后交换i和j的元素,然后j--,再开始从右向左寻找小于的元素

        if (i<j)

            swap(r[i], r[j--]);

    }

    return i;

}

void QuickSort(int R[], int low, int high)

{

    //先从一堆元素中找到一个基准元素,然后以这个基准元素为准,左侧都小于它,右侧都大于它。然后再对左侧和右侧分别进行快速排序。

    int mid;

    if (low < high)

    {

        mid = Partition(R, low, high);

        QuickSort(R, low, mid - 1);//左侧快速排序

        QuickSort(R, mid + 1, high);//右侧快速排序

    }

}

 

4.复杂度分析

1.时间复杂度分析

(1)最好时间复杂度

①分解:O(n);

②解决子问题:在最理想情况下,每次将问题划分为规模相当的两个子序列,也就是规模为n/2,即求解两个规模为n/2的子问题,所需时间为2T(n/2);

③合并:没有任何操作,不需要时间复杂度。

所以

经过递归求解(规模为1,令n=2x,则x=logn),所以T(n)=O(nlogn)。

(2)最坏时间复杂度

①分解:O(n);

②解决子问题:在最坏情况下,基准元素的一侧无元素,另一次有1个规模为n-1的子问题,那么递归出来所需要的时间为T(n-1);

③合并:没有任何操作,不需要时间复杂度。

所以

所以T(n)=O(n2)。

空间复杂度:O(n)

(3)平均时间复杂度:O(nlogn)

5.算法优化扩展

上述算法都是每次交换与基准元素进行交换,实际上没必要这样,我们的目的就是把原序列分为以基准元素为界的两个子序列,左侧子序列小于等于基准元素,右侧子序列大于基准元素。步骤如下:

步骤1:首先取数据第一个元素作为基准元素pivot=R[low]。i=low, j=high。

步骤2:从右向左扫描,找小于等于pivot的数R[j]。

步骤3:从左向右扫描,找大于pivot的数R[i]。

步骤4:R[i]和R[j]交换,然后i++, j--。

步骤5:重复步骤2~步骤4,直到i和j相等,如果R[i]大于pivot,则R[i-1]和基准元素R[low]交换,返回该位置mid=i-1;否则R[i]跟基准元素交换,返回该位置mid=i,该位置的数正好是基准元素。

至此完成一趟排序。此时以mid为界,左侧子序列均小于pivot,右侧子序列均大于pivot。

代码如下:

int Partition2(int r[],int low, int high)

{

    int i = low, j = high;

    int pivot = r[low];

    while (i < j)

    {

        while (i<j && r[j]>pivot)

            j--;

        while (i < j && r[i] <= pivot)

            i++;

        if (i < j)

        {

            swap(r[i++], r[j--]);

        }

    }

    if (r[i] > pivot)

    {

        swap(r[i - 1], r[low]);

        return i - 1;

    }

    swap(r[i], r[low]);

    return i;



}

 

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 二分法 分治法 合并排序 快速排序 算法学习
最后更新:2018年12月7日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
《ultraman china》第三话新的英雄(上) 张玉帅2018年9月——2019年1月总体规划 解析动态规划问题(2) 计算机组成原理笔记第五章(5.5) 网络技术与应用附录1:网络分类 在微机课写日志
标签聚合
算法 leetcode linux 鸟哥的linux私房菜 高中 Python Java python学习 生活 学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号