标签: complexity-theory

我正在研究数据挖掘,更确切地说是决策树.

我想知道是否有多种算法来构建决策树(或只有一个？),哪个更好,基于诸如

• 性能
• 复杂
• 决策失误
• 和更多.

如果LinkedHashMap的时间复杂度与HashMap的复杂性相同,为什么我们需要HashMap？与Java中的HashMap相比,LinkedHashMap的额外开销是多少？

我正在研究学校的时间复杂度,我们的主要关注点似乎是多项式时间 O(n^c)算法和准线性时间 O(nlog(n))算法,偶尔的指数时间 O(c^n)算法作为运行时透视的一个例子.然而,从未涉及处理更大的时间复杂性.

我想看一个在阶乘时间内 运行的算法解决方案的示例问题O(n!).该算法可能是一种解决问题的简单方法,但不能人为膨胀以在因子时间运行.

如果因子时间算法是解决问题的最着名的算法,则额外的街道信誉.

证明

1 + 1/2 + 1/3 + ... + 1/n is O(log n). 
Assume n = 2^k

我把这个系列放到了总和中,但我不知道如何解决这个问题.任何帮助表示赞赏

Drupal是一个"尽力而为"的CMS.有些模块允许您添加几乎任何功能,这很棒.但是,感觉很多功能(v5和v6)似乎散落在用户身上并且不直观.作为一名开发人员,我留下了使用泡泡糖和字符串拼凑一个网站的感觉.

例如,要将文本添加到默认搜索框(单击时消失),您必须添加一些jQuery代码或覆盖主题.我还发现菜单系统比它应该更复杂.

我是唯一有此意见的人吗？关于Drupal的核心你会改变什么(如果有的话)？

假设我们有以下Haskell:

data T = T0 | T1 | T2 | ... | TN

toInt :: T -> Int
toInt t = case t of
  T0 -> 0
  T1 -> 1
  T2 -> 2
  ...
  TN -> N

在这里使用什么算法来执行模式匹配？我看到两个选择:

(1)线性搜索,类似于

if      (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...

(2)二进制搜索,在这个特定任务中是明智的:在t.tag集合{ TO... T1023}中搜索.但是,在模式匹配通常具有许多其他功能和概括的情况下,可能不会使用此功能.

使用GHC进行编译,使用什么算法,对于模式匹配,使用N的时间复杂度t是toInt多少？

假设我有一个数字数组: [2,3,3,4,2,2,5,6,7,2]

找到该数组中最小值或最大值的最佳方法是什么？

现在,为了获得最大值,我循环遍历数组,并将变量重置为该值,如果它大于现有值:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

这似乎不是执行此操作的最佳方式(我尽可能避免循环).

给定一系列操作:

A*B*A*B*A*A*B*A*B

有没有办法获得最佳细分以启用子串的重用.

制造

a*b*a*b*a*a*b*a*b => c*a*c,其中c = a*b*a*b

然后看到了

a*b*a*b => d*d,其中d = a*b

总而言之,将8个初始操作减少到这里描述的4个？

(c =(d = a*b)*d)*a*c

当然,目标是尽量减少操作次数

我正在考虑各种后缀.

我对线性时间启发式或解决方案特别感兴趣.'*'操作实际上是矩阵乘法.

什么是计算机科学家对"幼稚实施"的意思最清楚的解释？我需要一个很好的清晰的例子来说明 - 理想情况下,即使是非技术人员 - 这种天真的实现在技术上可能是解决问题的有效方法,但实际上完全无法使用.

要构建一个后缀树,在最坏的情况下,如果字符串的所有字母都不同,那么复杂性将是类似的

n + (n-1) + (n-2) ... 1 = n*(n+1)/2

这是O(n ^ 2).

但是根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要花费O(n)时间.我在这里错过了什么？