在CLRS一书中,在第69页中,nC2表示单位除并征服(U-4)中的Θ(n ^ 2).任何人都可以谴责这个结果是如何真实的吗？
试图解决这个递归:
T(n) = 4T(n/2) + 2500 - sqrt(n)
here a = 4, b=2 but my f(n) = 2500 -sqrt(n)
n^ logb(a) = n ^ log2 (4) = n ^2
但f(n)是常数-sqrt(n)
我的问题:
我可以假设f(n)= Theta(sqrt n)或者我应该知道一些技巧吗？
此外,当你在它时,如果你能解释是否有一个常数减去sqrt(n)即减号有什么意义？或者它可以忽略.
这真让我抓狂!请帮忙!谢谢!!
众所周知,R不是运行大型分析的最有效平台.如果我有一个包含三个参数的大型数据框:
GROUP X Y
A 1 2
A 2 2
A 2 3
...
B 1 1
B 2 3
B 1 4
...
millions of rows
我想在每个组上运行计算(例如,在X,Y上计算Pearson的r)并将结果存储在一个新的数据框中,我可以这样做:
df = loadDataFrameFrom( someFile )
results = data.frame()
for ( g in unique( df$GROUP)) ){
gdf <- subset( df, df$GROUP == g )
partialRes <- slowStuff( gdf$X,gdf$Y )
results = rbind( results, data.frame( GROUP = g, RES = partialRes ) )
}
// results contains all the results here.
useResults(results)
显而易见的问题是,即使在强大的多核机器上,这也非常慢.
我的问题是:是否可以并行化这种计算,例如为每个组或一组组创建一个单独的线程？是否有一个干净的R模式来解决这个简单的除法和问题？ …
我想返回排序数组中重复值的数量.
例如:a = {1,1,2,3,4,4},fratelli(n)应返回2.(它们分别为1,1和4,4)
我试图使用递归方法,但它不起作用.它总是给我4.
我问是否有人可以帮助我更好地理解这种编程方法.非常感谢!
功能:
#include <iostream>
using namespace std;
int fratelli(int a[], int l, int r)
{
if (l == r) return 0;
else
{
int c = (l+r) / 2;
int n = fratelli(a, l, c) + fratelli(a, c+1, r);
if (a[l] == a[l+1]) n++;
return n;
}
}
int main()
{
const int _N = 11;
int array[_N] = { 1, 1, 2, 3, 5, 5, 7, 8, 8, 11, 12 };
cout << "\n" …我刚刚编写了一些经典的分治算法,我提出了以下问题:(更多是好奇心)
不可否认,在许多情况下,分而治之算法比传统算法更快; 例如,在快速傅里叶变换中,它提高了从N ^ 2到Nlog2N的复杂度.然而,通过编码,我发现,由于"划分",我们有更多的子问题,这意味着我们必须创建更多的容器并在子问题上分配更多的记忆.考虑一下,在合并排序中,我们必须在每次递归中创建左右数组,而在快速傅里叶变换中,我们必须在每次递归中创建奇数和偶数数组.这意味着,我们必须在算法期间分配更多的内存.
所以,我的问题是,实际上,比如在C++中,当我们还必须增加内存分配的复杂性时,像分而治之类的算法真的会赢吗？(或者内存分配根本不需要运行时间,而且成本是零？)
谢谢你的协助!
通过使用分而治之的方法，如果我们反复将一个数组分成两半，直到它们的大小减少为两个 - 之后我们可以在 O(1) 时间内返回两半中的最小值。扩展该方法，为了分别合并两个子数组 A 和 B 及其最小值“a”和“b”，我们可以直接在 O(1) 时间内返回它们的最小值，从而使合并步骤成为常数时间操作。
这本质上意味着存在 logN 个级别，并且合并步骤的复杂度为 O(1)。那么这是否意味着使用该算法在未排序数组中查找最小值的复杂度是 O(logN) ？
另请参阅此讨论。