标签: complexity-theory

我正在尝试编写代码来检测矩阵是否是Hankel矩阵的排列,但除了非常慢的暴力之外我无法想到有效的解决方案.这是规格.

输入: n×n矩阵M,其条目为1或0.

输入格式:空格分隔的行.每行一行.例如

0 1 1 1
0 1 0 1
0 1 0 0
1 0 1 1

输出: M的行和列的排列,如果可能,则M是Hankel矩阵.Hankel矩阵具有恒定的倾斜对角线(正倾斜对角线).

当我说排列时,我的意思是我们可以将一个排列应用于行的顺序,并将一个可能不同的排列应用于列.

我会非常感谢任何想法.

给定[0..n ^ 3-1]范围内的n个整数的输入集,提供线性时间排序算法.

这是我星期四测试的评论,我不知道如何解决这个问题.

什么更快:插入优先级队列,还是追溯排序？

我正在生成一些我需要在最后排序的项目.我想知道,在复杂性方面更快的是:将它们直接插入priority_queue或类似的数据结构中,还是在结尾处使用排序算法？

这是我需要解决的计算机视觉问题的低调版本.假设给你参数n,q并且必须计算将整数0 ..(q-1)分配给n-by-n网格的元素的方式的数量,以便对于每个赋值,以下都是真的

1. 没有两个邻居(水平或垂直)获得相同的值.
2. 位置(i,j)的值为0
3. 位置(k,l)的值为0

由于没有给出(i,j,k,l),输出应该是上面的一个评估数组,每一个有效设置为(i,j,k,l)

蛮力方法如下.目标是获得一个有效的算法,适用于q <= 100和n <= 18.

def tuples(n,q):
  return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]

def isvalid(t,n):
  grid=[t[n*i:n*(i+1)] for i in range(n)];
  for r in range(n):
    for c in range(n):
      v=grid[r][c]
      left=grid[r][c-1] if c>0 else -1
      right=grid[r][c-1] if c<n-1 else -1
      top=grid[r-1][c] if r > 0 else -1
      bottom=grid[r+1][c] if r < n-1 else -1
      if v==left or v==right or v==top or v==bottom:
        return …

如果n给出数字,我如何找到可能的三角形总数？有没有什么方法能在不到一定的O(n^3)时间内完成这项工作？

我正在考虑a+b>c,b+c>a以及a+c>b成为三角形的条件.

在最近的一个周六早餐早餐谷歌漫画中,作者描述了一种名为Frog Sort的算法,用于对自然数列表进行排序.这个算法在漫画中有描述,但为了简单起见,我在这里重印了它:

1. 对于要排序的每个自然数,制作一个包含许多苍蝇的盒子.
2. 在每个盒子里放一只青蛙.
3. 虽然并非所有的青蛙都跳出了他们的盒子:
   1. 等青蛙跳出它的盒子.
   2. 记下最初放在盒子里的苍蝇数量.
4. 生成的数字序列是原始的数字列表,但是按排序顺序排列.

该算法假设所有青蛙都以相同的速度吃苍蝇.结果,从它的盒子里跳出来的第一只青蛙将是每只苍蝇数量最少的青蛙,第二只青蛙是第二只吃最多的苍蝇,等等.

在漫画的中间,老师问学生"什么是最大步数？",我解释为"这个算法终止所需的最大步数是多少？" 也就是说,算法的运行时间是多少？然后学生回答"log _frog(盒子)".

这是对该算法运行时的准确分析吗？或者作者错了？

如何找到不同Haskell函数的复杂性(就big-O而言)？

例如,复杂性是subsequences多少？

如果实际的量子计算成为现实,我想知道是否有任何基于NP完全问题的公钥加密算法,而不是整数分解或离散对数.

编辑:

请查看有关量子计算机的维基文章中的 "计算复杂性理论中的量子计算"部分 . 它指出量子计算机可以回答的问题类别(BQP)被认为比NP完全更容易.

编辑2:

"基于NP-complete"是表达我感兴趣的一种不好的方式.

我打算问的是一个公钥加密算法,其特性是任何破解加密的方法也可用于打破潜在的NP完全问题.这意味着破解加密证明P = NP.

对于我们在算法分析中遇到的大多数复杂性,我们通常只有一个单词:

• O(1) =="常数"
• O(log n) =="对数"
• O(n) =="线性"
• O(n^2) =="二次"
• O(n^3) =="立方"
• O(2^n) =="指数"

我们遇到O(n log n)具有一定规律性的复杂算法(想想所有算法都以排序复杂性为主)但据我所知,我们在英语中没有一个单词能用来指代那种复杂性.这是我的知识差距,还是我们关于计算复杂性的英语话语中的真正差距？

如何计算这些回溯算法的时间复杂度,它们是否具有相同的时间复杂度？如果不同怎么样？请详细解释并感谢您的帮助.

1. Hamiltonian cycle:

        bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
            /* base case: If all vertices are included in Hamiltonian Cycle */
            if (pos == V) {
                // And if there is an edge from the last included vertex to the
                // first vertex
                if ( graph[ path[pos-1] ][ path[0] ] == 1 )
                    return true;
                else
                    return false;
            }

            // Try different vertices as a next candidate in Hamiltonian Cycle.
            // We don't try for 0 as …