标签: complexity-theory

假设有一些数学背景,你会如何对天真的计算复杂性理论进行总体概述？

我正在寻找P = NP问题的解释.什么是P？什么是NP？什么是NP-Hard？

有时维基百科的编写就像读者已经理解了所涉及的所有概念一样.

我认为这可能是一个经典问题,但我不知道答案.一个程序可以输出自己的副本,如果有的话,是否有一个简短的程序来执行此操作？

我不接受"空程序"作为答案,我不接受有权访问自己的源代码的程序.相反,我在想这样的事情:

int main(int argc, char** argv){ printf("int main(argc, char** argv){ printf...

但我不知道如何继续......

我正在开发一个需要大量(~25万字词典)的安卓文字游戏应用程序.我需要:

• 合理快速查找例如恒定时间更好,需要每秒执行200次查找以解决单词拼图,并且可能更频繁地在0.2秒内进行20次查找以检查用户刚刚拼写的单词.

编辑:查询通常会问"在字典中吗？".我想在这个单词中支持最多两个通配符,但这很容易,只需生成通配符可能存在的所有可能的字母并检查生成的单词(即26*26查找带有两个通配符的单词) .

• 因为它是一个移动应用程序,使用尽可能少的内存并且只需要少量初始下载字典数据是首要任务.

我的第一次天真尝试使用了Java的HashMap类,这导致了内存不足异常.我已经研究过使用android上可用的SQL lite数据库,但这看起来有些过分.

做我需要的好方法是什么？

所以我知道时间的复杂性:

for(i;i<x;i++){
   for(y;y<x;y++){
      //code
   }
}

是n ^ 2

但会:

for(i;i<x;i++){
   //code
}
for(y;y<x;y++){
   //code
}

是n + n？

我一直想知道java中String/StringBuilder/StringBuffer的charAt函数的实现是什么的复杂性？那么StringBuffer/StringBuilder中的deleteCharAt()呢？

设A是一个大小的数组N.(i,j)如果i < j和,我们将几个索引称为"反向"A[i] > A[j]

我需要找到一个接收大小数组N(带有唯一数字)的算法,并返回时间的倒数O(n*log(n)).

存在大小为n的数组,并且数组中包含的元素在1和n-1之间,使得每个元素出现一次并且仅一个元素出现多次.我们需要找到这个元素.

虽然这是一个非常常见的问题,但我仍然没有找到合适的答案.大多数建议是我应该将数组中的所有元素相加,然后从中减去所有索引的总和,但如果元素的数量非常大,这将不起作用.它会溢出.关于XOR门的使用也有一些建议dup = dup ^ arr[i] ^ i,我不清楚.

我已经提出了这个算法,这是一个增加算法的增强,并将在很大程度上减少溢出的机会!

for i=0 to n-1
  begin :
    diff = A[i] - i;
    sum  = sum + diff;
  end

diff包含重复元素,但使用此方法我无法找到重复元素的索引.为此,我需要再次遍历数组,这是不可取的.任何人都可以提出一个更好的解决方案,不涉及添加方法或XOR方法在O(n)中工作？

我从未见过这种复杂性的符号:Õ(n).

它出现在随机算法学习的背景下.

有人知道这个符号吗？你不能完全google这个......

编辑:已解决

我想人们已经在下面指出了正确的答案.在我的例子中,Õ()用于隐藏树的指数增长.

我只是尝试用各种方法实现代码(在Java中),通过它可以计算斐波那契数列的第n项,并且我希望验证我学到了什么.

迭代实现如下:

public int iterativeFibonacci(int n)
{
  if ( n == 1 ) return 0;
  else if ( n == 2 ) return 1;
  int i = 0, j = 1, sum = 0;
  for ( ; (n-2) != 0; --n )
  {
    sum = i + j;
    i = j;
    j = sum;
  }
  return sum;
}

递归实现如下: -

  public int recursiveFibonacci(int n)
  {
    if ( n == 1 ) return 0;
    else if ( n == 2 ) …

设G(U u V,E)是加权有向二分图(即U和V是二分图的两组节点,E包含从U到V或从V到U的有向加权边).这是一个例子:

在这种情况下:

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)} 

定义: DirectionalMatching(我编写这个术语只是为了让事情变得更清晰):可以共享起点或终点顶点的有向边集.也就是说,如果U-> V和U' - > V'都属于DirectionalMatching,那么V/= U'和V'/ = U,但它可以是U = U'或V = V'.

我的问题:如何有效地找到如上定义的DirectionalMatching,用于最大化其边缘权重之和的二分方向加权图？

通过有效,我的意思是多项式复杂性或更快,我已经知道如何实现一个天真的蛮力方法.

在上面的示例中,最大加权DirectionalMatching是:{F-> A,C-> E,B-> D},值为13.

正式证明这个问题与图论中任何其他众所周知的问题的等价性也是有价值的.

谢谢!

注1: 此问题基于最大加权二分匹配_with_有向边,但具有额外的松弛,允许匹配中的边共享原点或目的地.由于这种放松有很大的不同,我创造了一个独立的问题.

注2:这是最大重量匹配.基数(存在多少条边)和匹配所覆盖的顶点数与正确的结果无关.只有最大重量才算重要.

注2:在我研究解决问题的过程中,我发现了这篇论文,我认为对其他人试图找到解决方案会有所帮助:边缘彩色多图中的交替周期和路径:一项调查

注3:如果有帮助,您还可以将图形视为等效的2边彩色无向二分多图.然后,问题公式将变为:找到没有颜色交替路径的边集或具有最大权重和的循环.

注4:我怀疑这个问题可能是NP难的,但我不是那种减少经验的人,所以我还没有成功证明这一点.

又一个例子:

想象一下你有

4个顶点: {u1, u2} {v1, v2}

4边: {u1->v1, u1->v2, u2->v1, v2->u2}

然后,不管他们的权重,u1->v2而v2->u2 …