标签: divide-and-conquer

这对我来说是一个算法游乐场!我已经看到这个问题的变化处理最大连续子序列,但这也是另一个变化.正式的def:给定的A[1..n]发现i,j因此abs(A[i]+A[i+1]+...+A[j])最接近于零.

我想知道如何获得O(n log^2 n),甚至O(n log n)解决方案.

我是新来的.作为一名研究生,我现在已经在算法上集思广益了一段时间.我感谢任何可以解决以下问题的帮助.我搜索得足够多,我找不到任何解决这个问题的方法.

我们有一组排序不同的数字,这些数字是无限长的.前n个数字是大于0但小于1的分数.所有剩余的元素都是"1",并且没有给出n的值.您需要开发一种算法来检查该数组中是否出现用户给定的分数F. 将算法的时间复杂度分析为n的函数.(n = 8的示例,其中1从数组的第8个位置开始)

我的方法:我猜测解决这个问题的最佳方法是使用二进制搜索.每次我们可以将数组的大小减半,最后到达要找到的分数.我们假设数组中有m个元素,包括1.分数元素的数量是n.在整个阵列上执行二进制搜索的时间复杂度是O(log(m)).由于我被要求用n表示时间复杂度,m = n + k(假设数组中1的数量是k)所以这个问题的时间复杂度是O(log(n + k)).

请投入你的想法.谢谢

我们如何从值创建节点集....

我有n个数字1,2,3 ....... n.

我想创建一个节点集

<MYNMUMS>
<MYNUM>1</MYNUM>
<MYNUM>2</MYNUM>
<MYNUM>3</MYNUM>
<MYNUM>4</MYNUM>
....
<MYNUM>N</MYNUM>
</MYNMUMS>

这学期我有一门算法课。一切都很好，直到我听到有关订单统计的讲座。

这是该讲座的第一张幻灯片：

Order Statistics\nSelect the ith smallest of n elements (the\nelement with rank i).\n\xe2\x80\xa2 i = 1: minimum;\n\xe2\x80\xa2 i = n: maximum;\n\xe2\x80\xa2 i = \xe2\x8e\xa3(n+1)/2\xe2\x8e\xa6 or \xe2\x8e\xa1(n+1)/2\xe2\x8e\xa4: median.\nNaive algorithm: Sort and index ith element.\nWorst-case running time = \xce\x98(n lg n) + \xce\x98(1)\n= \xce\x98(n lg n)\n

我无法理解以下内容：

什么是订单统计？

n 个元素中第 i 个最小的元素意味着什么？请我需要一个例子来知道什么是“ith”！！

关于这些有什么简单的解释吗？

我所知道的是，这与分而治之有关，因为下一张幻灯片就是关于它的:)。

对于硕士定理,T(n) = a*T(n/b) + f(n)我使用3个案例:

1. 如果a*f(n/b) = c*f(n)为某些常数c > 1那么T(n) = (n^log(b) a)
2. 如果a*f(n/b) = f(n)那么T(n) = (f(n) log(b) n)
3. 如果a*f(n/b) = c*f(n)为某些常数c < 1那么T(n) = (f(n))

但是当f(n) = log n或时n*log n,值c取决于n的值.如何使用master's定理求解递归函数？

我在分治算法方面遇到了一些麻烦,并且正在寻求一些帮助.我试图编写一个名为sumArray的函数来计算整数数组的总和.

此函数必须通过将数组分成两半并在每一半上执行递归调用来完成.我尝试使用类似的概念来编写递归求和算法时使用的概念,以及用于识别数组中最大元素的分而治之算法,但我正在努力将这两个想法结合起来.

下面是我为sumArray编写的代码,它编译但不返回正确的结果.

int sumArray(int anArray[], int size)
{
    int total = 0;
    //base case
    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

    //divide and conquer
    int mid = size / 2;
    int lsum = anArray [mid] + sumArray(anArray, --mid);
    int rsize = size - mid;
    int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize);
    return lsum + rsum;
}

我已经将问题确定为函数在计算rsum时包含lsum的值.我知道问题在于我使用rsize对sumArray的递归调用(一个等于原始数组大小的变量,减去中点).但是,出于某种原因,我似乎无法确定修复方法.

我觉得很傻,因为我知道答案是正确地盯着我看,但是如何修复我的功能以便它返回准确的结果呢？

更新:感谢所有有用的响应,我已修复我的代码,以便它编译和运行良好.我会留下我原来的代码,以防其他人在分裂和征服中挣扎,并可能犯同样的错误.有关正确解决问题的函数,请参阅@Laura M的答案.@haris的回复也很好地解释了我的代码出现错误的地方.

我编写了这个算法，用于查找大小为 N 的数组中的 MAX 数：

find_max (s,e,A){
if (s != e){
    mid = floor((e-s)/2) + s;
    a = find_max(s,mid,A);
    b = find_max(mid + 1, e,A);
    if (a > b){
        return a;
    }
    return b;
}
return A[s];

}

我想知道时间成本、T(n) 方程以及该算法是否渐近更大、更快或相当于非分而治之策略（顺序比较每个数字）。

我想出了一些答案，但我认为它们都不正确。

谢谢你！

在无向图 G=(V,E) 中，顶点被着色为红色、黄色或绿色。此外，存在一种将图划分为两个子集的方法，使得 |V1|=|V2| 或 |V1|=|V2|+1 其中以下条件适用：V1 的每个顶点都连接到 V2 的每个顶点，或者 V1 的顶点没有连接到 V2 的顶点。这递归地适用于 V1 和 V2 的所有诱导子图

我可以通过将邻接矩阵与其自身相乘三倍并逐步增加与主对角线的非零条目相对应的节点来找到图中的所有三角形。然后我可以查看三角形的节点是否以正确的方式着色。O(n^~2,8)！但是考虑到图形的独特属性，我想使用分治法找到一个解决方案来找到彩色三角形。这是具有给定属性的示例图。我需要找到粗体三角形： 蓝色框表示分区完全连接，紫色框表示分区之间没有连接

为了使动态规划适用，问题必须具有两个关键属性：最优子结构和重叠子问题 [1]。对于这个问题，我们将只关注后一个属性。

重叠子问题有多种定义，其中两个是：

• 如果问题可以分解为多次重复使用的子问题，或者该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 [2]，则称该问题具有重叠的子问题。
• 要应用动态规划，优化问题必须具备的第二个要素是子问题的空间必须“小”，因为该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题（CLRS算法介绍）

如果找到解决方案涉及多次解决相同的子问题，那么这两个定义（以及互联网上的许多其他定义）似乎都可以归结为具有重叠子问题的问题。换句话说，在寻找原始问题的解决方案的过程中，有许多小的子问题被多次计算。一个经典的例子是斐波那契算法，很多例子都用来让人们理解这个属性。

直到几天前，生活都很棒，直到我发现了Kadane 的算法，这让我质疑重叠的子问题定义。这主要是因为人们对它是否是 DP 算法有不同的看法：

• Kadane 算法中的动态规划方面
• Kadane 的算法是否考虑 DP？以及如何递归地实现它？
• Kadane 的算法是贪心算法还是优化 DP？
• 动态编程与记忆化（见我的评论）

有人不认为 Kadane 的算法是 DP 算法的最令人信服的原因是每个子问题只会在递归实现中出现和计算一次[3]，因此它不包含重叠子问题的属性。然而，互联网上的很多文章都认为 Kadane 的算法是一种 DP 算法，这让我怀疑我对重叠子问题的理解首先意味着什么。

人们似乎对重叠子问题的属性有不同的解释。使用简单的问题（例如斐波那契算法）很容易看到它，但是一旦您介绍了 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供一些进一步的解释，我将不胜感激。

我有一个分数，我想打印它的乳胶形式。对于 n == 3，分数如下：

如何使用分治法打印该分数的乳胶： 1+\frac{2+\frac{4}{5}}{3+\frac{6}{7}}

对于 n == 4，分数是：

结果是： 1+\frac{2+\frac{4+\frac{8}{9}}{5+\frac{10}{11}}}{3+\frac{6+\frac{12}{13}}{7+\frac{14}{15}}}