分治法的基本思想在上回的递归中已经讲的差不多了。 就是将规模较大的问题分解成规模较小的问题。
T(n) = aT(n/b) + f(n) (a>=1; b>1)
T(n) 就是规模为n的问题, 可以分解成a个规模为n/b的同类型的问题, 再加上分解过程的开销(汉诺塔的move, 布尔组合的set value)。
虽说对无序的序列采取分治没什么意义, 但这里仅仅只是用来说明分治的思想, 故例与此。
例: 从数组中找出最大、最小值
【方法一】
int min = a[0], max = a[0];
for(int i = 1; i < a.length; i++) {
if(a[i] < min) min = a[i];
if(a[i] > max) max = a[i];
}
一共 2×n-2 次比较。
【方法二】
public class FindMinMax {
private static int MIN;
private static int MAX;
public static void main(String[] args) {
int[] a = new int[] { 6, -111112, 1, 7, 4, 8, 2, 0, 100, 12, -100, -1, -43, 1912, 11, 77, -9999 };
MIN = MAX = a[0];
int[] res = find(a, 1, a.length - 1);
System.out.println("Min: " + res[0]);
System.out.println("Max: " + res[1]);
}
private static int[] find(int[] a, int from, int to) {
if (from + 1 == to || from == to) {
if (a[from] < a[to]) {
MIN = MIN < a[from] ? MIN : a[from];
MAX = MAX > a[to] ? MAX : a[to];
} else {
MIN = MIN < a[to] ? MIN : a[to];
MAX = MAX > a[from] ? MAX : a[from];
}
} else {
int mid = (from + to) / 2;
find(a, from, mid);
find(a, mid + 1, to);
}
return new int[] { MIN, MAX };
}
}
一共3n/2-2次比较。
所以从效率上还是比遍历稍好些。
对于分治法的其他些算法如: 二分查找, 快排, 归并, 插入等以后再补充。
-------------------------- 我是分割线 ----------------------------
分享到:
相关推荐
"分治法求最大值和最小值" 在这篇实验报告中,我们将通过分治法来解决最大值和最小值的问题。分治法是一种将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 实验目的: * ...
### 分治法求两个大整数相乘 #### 一、问题背景及描述 在计算机科学领域,处理大整数的运算是一项常见的需求,尤其是在密码学、数据加密以及某些科学计算场景中。对于传统整数类型(如 `int`, `long` 等)无法表示...
**标题解析:**“分治法求最近点对”指的是使用分治策略来解决寻找二维空间中距离最近的两个点的问题。在计算机科学中,分治法是一种将复杂问题分解成更小、易于处理的部分的方法,然后分别解决这些部分,最后合并...
### 分治法求解两个有序数组的中位数 #### 分治法简介 分治法是一种重要的算法设计思想,其核心在于将一个复杂的问题分解成若干个规模较小但结构相似的子问题,然后递归地解决这些子问题,并将各个子问题的解组合...
**实验4 分治法1** 分治法是计算机科学中一种重要的算法设计策略,它将一个大问题分解为若干个小问题来解决。这种思想源于“分而治之”,旨在通过解决小规模问题来构建大规模问题的解决方案。在这个实验中,我们将...
最大子段和(分治法)源码 本资源是一个关于最大子段和问题的解决方案,使用了分治法来解决该问题。最大子段和问题是指给定一个由 n 个整数(可能有负整数)组成的序列(a1, a2, …, an),求该序列中的最大子段和...
分治法是一种常用的问题求解策略,特别是在处理复杂问题时能有效降低计算复杂度和问题规模。在空中飞行管理问题上,飞行安全是至关重要的,其中一项挑战就是预先识别出哪两架飞机之间存在最大的碰撞风险。如果能够...
在计算机科学领域,分治法(Divide and Conquer)是一种高效的问题解决策略,它将一个复杂的大问题分解成若干个相同或相似的子问题,直到这些子问题变得足够简单,可以直接求解为止。这种方法在处理诸如排序、查找...
分治法是解决复杂问题的一种策略,它将一个大问题分解为若干个规模较小的相同或相似的子问题,然后分别解决这些子问题,最后再合并子问题的解来得到原问题的解。在01背包问题中,分治法的应用并不直接,但可以通过...
在这个题目中,我们要探讨的是"最大字段和问题",这是一个经典的算法问题,通常用分治法(Divide and Conquer)来解决。下面将详细介绍这个问题及其解决方案。 **最大字段和问题**,也被称为**最大子序列和问题**,...
### 分治法求最近点对问题 #### 实验目的与内容概述 本次实验的主要目标是理解和实现分治法解决最近点对问题。具体任务包括: 1. **最近点对问题**:给定平面上的N个点,找到其中两点间的最小距离。 2. **随机...
**分治法(Divide and Conquer)**是一种重要的算法设计策略,在计算机科学中广泛应用于解决复杂问题。这种策略的基本思想是将一个大问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题,然后分别解决子...
**分治法求众数** 分治法是一种重要的算法设计策略,它将复杂的问题分解成较小的子问题,然后递归地解决这些子问题,最后将子问题的解合并成原问题的解。在这个实验中,我们应用分治法来寻找数组中的众数,即出现...
在编程领域,分治法是一种常用的算法设计策略,它的核心思想是将复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个过程可以递归进行,从而...
下面我们将深入探讨解决这一问题的三种主要方法:蛮力法、分治法和动态规划法。 1. **蛮力法**: 蛮力法是最直观的解法,通过遍历所有可能的子序列来找出最大和。对于长度为n的数组,我们需要检查n*(n+1)/2个子...
分治法是一种解决复杂问题的有效策略,它将大问题分解为小问题来解决,然后合并小问题的解得到大问题的解。本篇文章将详细讨论如何利用分治法实现矩阵相乘。 矩阵相乘的基本概念是,两个矩阵A(m×n)和B(n×p)...
分治法是一种重要的算法设计策略,它将一个大问题分解为若干个规模较小的相同或相似的子问题,然后分别解决这些子问题,最后将子问题的解组合得到原问题的解。在“平面最接近点对问题”中,我们的目标是找到一组二维...
3. 要求随机生成N个点的平面坐标,应用分治法编程计算出所有点对的最短距离。4. 分别对N=100100010000100000,统计算法运行时间,比较理论效率与实测效率的差异,同时对蛮力法和分治法的算法效率进行分析和比较。5. ...
在本实验报告中,我们将深入探讨如何使用分治法来优化矩阵乘法的效率,这一方法是算法设计与分析的重要组成部分。我们将使用C++编程语言实现这一算法。 分治法是一种解决问题的有效策略,它将复杂的问题分解为较小...