divide-and-conquer

    1热度

    1回答

    解释nC2是如何在Θ（n^2）

    在书CLRS，在第69页，它说，在单位分而治之（U - 4）nC2是Θ（n^2）。任何人都可以expalin如何这个结果是真实的？
    algorithm divide-and-conquer clrs 2014-06-20

    1热度

    3回答

    n个对象的等价测试

    假设我们给了'n'个对象和一个接受两个输入的子例程，并说它们是否相等（例如，如果它们相等，它可以给出输出为1）。 我需要想出一个算法，它调用上述函数O（n log n）次并决定输入是否有多于'n/2'的项目彼此等效。
    algorithm recursion divide-and-conquer 2014-10-02

    1热度

    1回答

    分而治之算法的属性示例

    我在理解分而治之算法的以下属性时遇到了问题。 划分大小N的问题分解成两个独立的 （非空），该解决了递归调用自身小于N倍份的递归方法。 证明是 递归函数划分大小N的问题分解成两个独立的 （非空），该解决了递归调用自身小于N倍份。 如果这些部件是尺寸为k和尺寸为N-k中的一个，则我们使用的递归调用总数为T(n) = T(k) + T(n-k) + 1，对于N>=1和T(1) = 0的总数为 。 解决方
    algorithm recursion divide-and-conquer 2014-01-30

    0热度

    1回答

    合并排序实现洗牌阵列但不排序

    我是一名初学者程序员。这是我在Java中实现的MergeSort算法。 我似乎无法修复这个错误。 数组被洗牌但未被排序。有人能指出我的错吗？ public static int[] divide(int a[], int n, int low, int high) { if (low == high) { int[] b = { a[low] }; return b;
    java sorting merge divide-and-conquer 2014-01-31

    2热度

    1回答

    分而治之算法：找到一个矩阵的最小值

    我开始学习如何实现分治算法，但是我在这个练习中遇到了一些严重的麻烦。 我已经写指找到使用分在给定的矢量的最小值的算法和方法克服： int minimum (int v[], int inf, int sup) { int med, m1, m2; if (inf == sup) return v[inf]; med = (inf+sup)/2; m1 = minimum (v, inf
    c++ recursion matrix divide-and-conquer 2014-07-03

    0热度

    3回答

    使用第一个元素作为支点快速排序

    我通过选择第一个元素作为支点，实现了快速排序。它适用于一般的测试用例，但考虑一个例子，当数组被反向排序时，例如5 4 3 2 1.我知道它在哪里抛出运行时错误。但我无法正确解决它。第一个元素的实现是否正确？请提出修改建议。 public static void quicksort(int low,int high) { if(low<high) { int
    java algorithm pivot quicksort divide-and-conquer 2014-09-01

    1热度

    1回答

    平方矩阵和运行时间

    我可以证明矩阵A的2 * 2的平方是O（n^log5），表明它只需要5次乘法。直到现在我没有问题，但在我想解释2个原因之后，为什么我们无法概括为其他情况下的平方（不同的n * n大小），我可以拿出一个如下： 第一个我能想到的原因是我乘以例如3 * 3矩阵与自己，并得出结论，至少它有6个乘法，所以它的运行时间至少是O（n^log6），其中n^epson大于O（n^log5），所以它比较慢，我们不能概
    algorithm big-o divide-and-conquer big-theta 2014-02-22

    1热度

    1回答

    分而治之 - 在包含独特元素的两个相同大小的数组之间找到中值？

    我试图解决正是这样一个问题： nth smallest number among two databases of size n each using divide and conquer 从我能想出的“比较中位数/中位数的中位数”算法将给我们的解决方案吗？ 我的问题是我是否正确理解这一点。 array 1: [7 8 6 5 3] array 2: [4 10 1 2 9] 首先，找到每个
    algorithm divide-and-conquer 2014-02-24

    2热度

    1回答

    了解递归/子问题如何组合（最大子数组算法）

    我在理解分治算法时遇到了一些问题。我已经读过，为了成功地应用递归，你需要有一个“递归的信仰飞跃”，你不应该为每一步的细节而烦恼，但我并不满足于接受递归如果全部条件得到了满足，因为这对我来说似乎很神奇，我想了解它为什么会起作用。 所以我给出的伪代码查找最大子阵列的下列递归算法： Find-Maximum-Subarray(A, low, high) if high == low retu
    algorithm recursion divide-and-conquer 2014-04-15

    -3热度

    1回答

    最近的一对点使用分而治之算法来计算在合并阶段只有6点

    这是一个问题出现在科尔曼的Algos介绍的基础上找到最接近的一对点，其中Y'属于垂直带距离线“l”至少有一些“三角”距离的点。 d是除法和征服阶段计算的任意一对点之间的最小距离。 P是点的集合，PL是分割后的左边的点集合，PR是正确的点集合。 威廉姆斯教授提出了一种方案，允许最接近对算法仅检查数组Y'中每个点之后的5个点。这个想法总是将第l行的点放入PL中。然后，在线l上不能有一对重合点，一个在P
    algorithm computational-geometry divide-and-conquer 2014-02-25
最新问题