【算法学习】减治 · 分治 · 变治(二)

简介: 【算法学习】减治 · 分治 · 变治

2.减去一个常数因子(decrease by a constant factor)

 

减去常数因子实际上就是把规模除以一个常数。(在多数情况下,这个常数因子是二)

微信图片_20220422145135.png

继续以计算f(n)=a^n为栗:

微信图片_20220422145137.jpg这里的时间复杂度为O (log n),就比蛮力法优化多了。


对分查找,假币问题都可以用这种思想。我们以假币问题为例:

有n枚银币,其中有1枚是假的,假币重量偏重、偏轻未知,输入银币的重量,求假币的位置。


我们先取出一枚银币作为对照,再将银币分为两半称重,每次称重对比,再从有问题的一堆中继续称重查找。这样,每次我们都减去了常量因子2。

当然,银币总数是奇偶时需要不同的处理方式,在银币数量为偶数时,由于不知道假币偏轻或偏重,我们需要选择一个compare进行对照。

 

同时,我们还可以把银币分为三堆考虑,进一步优化时间复杂度。(作为代价,代码要考虑总数mode3余1、2、0的情况,同时要比较三堆,会稍稍复杂一些)

 

Codding time:


//三分法求八枚银币问题
#include <iostream>
using namespace std;
int coin[105],num;
int sum(int left, int right)
{
    int sum = 0;
    for (int i = left; i <= right; i++)
        sum += coin[i];
    return sum;
}
int findfake(int left, int right)
{
  int n=right-left+1;
    int p1=(right+left)/3;
    int p2=p1*2;
    int sign = n % 3;
    if (sign == 0)
    {
        int fake = 0;
        int A, B, C;
        A = sum(left,p1);
        B = sum(p1+1,p2);
        C = sum(p2+1,right);
        if (n == 3)
        {
            if (A == B)
            {
                fake = right;
            }
            else if (A == C)
            {
                fake = right - 1;
            }
            else
            {
                fake = left;
            }
            return fake;
        }
        else
        {
            if (A == B)
            {
                fake = findfake(p2+1,right);
                return fake;
            }
            else if (A == C)
            {
                fake = findfake(p1+1,p2);
                return fake;
            }
            else
            {
                fake = findfake(left,p1);
                return fake;
            }
        }
    }
    if (sign == 1)
    {
        int fake = right;
        int A, B, C;
        A = sum(left,p1);
        B = sum(p1+1,p2);
        C = sum(p2+1,right-1);
        if (n == 1)
        {
            return fake;
        }
        else
        {
            if (A == B)
            {
                if (A == C)
                    return fake;
                if (A !=C)
                {
                    fake = findfake(p2+1,right-1);
                    return fake;
                }
            }
            else if (A == C)
            {
                fake = findfake(p1+1,p2);
                return fake;
            }
            else
            {
                fake = findfake(left,p1);
                return fake;
            }
        }
    }
    if (sign == 2)
    {
        int fake = 0;
        int x1 = right - 1;
        int x2=right;
        int A, B, C;
        A = sum(left,p1);
        B = sum(p1+1,p2);
        C = sum(p2+1,right-2);
        if (n == 2)
        {
            int campare; //参照物
            if (right != num)
                campare = coin[num];
            else
                campare = coin[1];
            if (coin[x2] == campare)
                fake = x1;
            else
                fake = x2;
            return fake;
        }
        else
        {
            if (A == B && B == C)
            {
                int campare = coin[0];
                if (coin[x1] == campare)
                    fake = x2;
                else
                    fake = x1;
                return fake;
            }
            else if ((A == B) && (A!=C))
            {
                fake=findfake(p2+1,x1-1);
                return fake;
            }
            else if (A == C)
            {
                fake=findfake(p1+1,p2);
                return fake;
            }
            else
            {
                fake = findfake(left,p1);
                return fake;
            }
        }
    }
    return 0;
}
int main()
{
  cin >> num;
  for (int i = 1; i <= num; i++)
    cin >> coin[i];
    int fake=findfake(1,num);
  cout << fake;
    return 0;
}

微信图片_20220422145251.png

 

3.减去的规模是可变的(variable size decrease)

 

字面理解,就是指每次减去的规模的模式或数值是不同的

微信图片_20220422145254.png

这里我们拿欧几里德算法为栗子。学过数论的盆友们知道(数学害人不浅啊),欧几里得算法是一种求最大公约数的较为简便的方法,也叫辗转相除法。用一个简单的式子来表示:

 

gcd(a,b) = gcd(b,a mod b) (这里a>b)

(题外话,我记得数论里最大公约数是不需要gcd的。。。)

 

可以大致想象到,这里每次减去的规模是完全未知、可变的。

 

我们再举一个栗子:二叉查找树。

 

百度百科告诉我们,二叉查找树是一颗这样的树:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

(4)没有键值相等的结点。

 

根据树的性质,我们可以发现对二叉查找树的查找并不困难,只要从顶点开始不断比较就行了。但二叉查找树不一定就是平衡二叉树,如果只有一个分支,那减去的规模就会变化。(为什么我感觉解释的好扯啊。。。)

 

查找的代码并不困难,我们这里只给出实现插入和查找两种功能的代码。

(就当练习数据结构了= =)

 

Coding time:


//二叉排序树 
#include <iostream>
using namespace std;
typedef class BiTNode  //定义结点类,指针类型名 
{
public:
  int data;
  class BiTNode *leftchild, *rightchild;
}*BiTree;
// BST查找,查找成功,则p指向该元素节点,返回true
bool searchBST(BiTree T,int key,BiTree f,BiTree &p)
{
  if (!T)
  {
    p = f;
    return false;
  }
  else if (key == T->data)
  {
    p = T;
    return true;
  }
  else if (key < T->data)
    return searchBST(T->leftchild, key, T, p);
  else
    return searchBST(T->rightchild, key, T, p);
}
//BST插入,用于建立树 
bool insertBST(BiTree &T, int key)
{
  BiTree p, s;
  //因为在searchBST的过程中有进行比较,所以search完T就指向该插入位置的父结点 
  if (!searchBST(T, key,NULL, p))
  {
    s = new BiTNode;
    s->data = key;
    s->leftchild = s->rightchild = NULL;
    if (!p)  T = s;      //p是空的说明树是空的,则插入在根节点
    else if(key < p->data) p->leftchild = s;
    else     p->rightchild = s;
    return true;
  }
  else
    return false;
}
int main()
{
    //二叉树的创建
    int n;
    cout<<"输入点个数"<<endl;
    cin>>n;
    BiTree T = NULL;
    cout<<"输入节点"<<endl;
    for (int i = 0; i < n; i++)
    {
      int a;
      cin>>a;
      insertBST(T, a);
    }
    //二叉树的查找
    BiTree p=NULL;
    BiTree f=NULL;
    cout<<"接下来进行二叉排序树的查找,请输入值key"<<endl;
    int key;
    cin>>key;
    if (searchBST(T, key, f, p))
      cout<<"在二叉排序树中"<<endl;
    else
      cout<<"不在二叉排序树中"<<endl;
        return 0;
}

微信图片_20220422145256.png

emmm,这图好像看不出什么。


编写的过程中有一点小插曲,我看错了树的定义,所以一开始的版本出现了错误(┬_┬),可以放出来给无聊的人看看,找找错。(说明看对题目真的很重要!!!)

 

wrong code:


//二叉查找树的建立(数组实现) 
#include <iostream>
using namespace std; 
int size=0;  //size为树的规模 
int tree[1005]; 
const int INF=0;
void addElement(int element)
{
    int p = 1; //指标p 
    if(size == 0)
    {
        tree[p] = element;
        size++;
        return;
    }
    while(true)
  {
        if(element<tree[p])
        {
            int p1 = 2 * p  ;   //p1指向p的左儿子的位置   
            if(tree[p1] == INF)
      {
        tree[p1] = element;
        size++;
        return;
      }
            else 
          p = p1;
        }        
        else
        {
            int p2 = 2 * p + 1;  //p2指向p的右儿子的位置 
            if(tree[p2] == INF)
      {
              tree[p2] = element;
              size++;
        return;
      }
            else   
          p = p2;
        }        
    }
} 
int main()
{
  int i,j=1;
  for (i=1;i<=size;i++)
      tree[i]=INF;
  int temp;
  while(cin>>temp)
  {
    addElement(temp);
  }
  for (i=1;j<=size;i++)
  {
    if(tree[i]!=INF)  
    {
      cout<<tree[i]<<"   ";
      j++;
    }
  }
  return 0;
}


相关文章
|
2月前
|
机器学习/深度学习 算法 数据挖掘
没发论文的注意啦!重磅更新!GWO-BP-AdaBoost预测!灰狼优化、人工神经网络与AdaBoost集成学习算法预测研究(Matlab代码实现)
没发论文的注意啦!重磅更新!GWO-BP-AdaBoost预测!灰狼优化、人工神经网络与AdaBoost集成学习算法预测研究(Matlab代码实现)
|
27天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
118 1
|
8月前
|
算法 搜索推荐 Java
算法系列之分治算法
分治算法(Divide and Conquer)是一种解决复杂问题的非常实用的策略,广泛应用于计算机科学中的各个领域。它的核心思想是将一个复杂的问题分解成若干个相同或相似的子问题,递归地解决这些子问题,然后将子问题的解合并,最终得到原问题的解。分治算法的典型应用包括归并排序、快速排序、二分查找等。
260 72
 算法系列之分治算法
|
7月前
|
算法 数据可视化 开发者
为什么要学习数据结构与算法
今天,我向大家介绍一门非常重要的课程——《数据结构与算法》。这门课不仅是计算机学科的核心,更是每一位开发者从“小白”迈向“高手”的必经之路。
为什么要学习数据结构与算法
|
9月前
|
负载均衡 算法
架构学习:7种负载均衡算法策略
四层负载均衡包括数据链路层、网络层和应用层负载均衡。数据链路层通过修改MAC地址转发帧;网络层通过改变IP地址实现数据包转发;应用层有多种策略,如轮循、权重轮循、随机、权重随机、一致性哈希、响应速度和最少连接数均衡,确保请求合理分配到服务器,提升性能与稳定性。
1947 11
架构学习:7种负载均衡算法策略
|
10月前
|
供应链 算法
【算法】——快排,分治算法合集
本文主要介绍排序中的快排思想的应用,做到一法通万法的效果
102 16
|
11月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
11月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
219 2
|
22天前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
137 3

热门文章

最新文章