complexity-theory

0热度

2回答

嗨，我面临一个问题，证明函数是一个大的theta元素。问题如下：是4n^3 + 23n^2 + 1（是Theta（n^3）的一个元素），并证明你的答案。我的回答如下：基本上我证明它是在大哦和大欧米茄，如果是的话，它是在大θ。它是否正确？此外，证明给定函数在使用极限的big theta中的最佳方式是什么？

2热度

2回答

使用最小优先级队列的复杂性问题

我是数据结构类的学生，目前的任务是创建一个最小优先级队列，我已经完成并测试了，并且据我所知，它可以工作。我的问题是，我们还需要安排我们的课程并分析他们的Big-O复杂性;我设计了一个授课班（我为过去的任务完成），收集数据并绘制它。我的deleteMin和add方法的复杂度应该是O（logn），而findMin应该有O（c），但是我的add方法由于某种原因返回O（c）。由于我已经重复测试了minPQ

4热度

1回答

实验测定计算矩阵的复杂性决定

我需要帮助确定实验矩阵的行列式的计算复杂度为n×n 我的代码： import numpy as np import timeit t0 = time.time() for n in range(1, 10): A = np.random.rand(n, n) det = np.linalg.slogdet(A) t = timeit

1热度

1回答

算法概率游戏的问题

我开始开发为契机游戏的问题如下规则的算法：在游戏开始时，玩家起始如果s开始（开始）。他从掷骰子开始并提前指定空格数。骰子的可能值从1到6 然后玩家执行于当前的情况下（事先指定的动作，回去，relance骰子（如果当前的情况是R：Relance ））。每个动作花费1回合。当玩家达到完成情况E时结束游戏（结束）。玩家必须完全落在终点线上，并且不能超过终点线。开始和结束情况S和E不一定在托盘

0热度

1回答

整数序列的C++有效比较（相对顺序）

我将非常感谢在C++中有效实现比较算法的帮助。我的程序获取由整数序列行组成的输入，我需要找出哪些序列是重复的。但是一些序列可能会转移到一边，它应该仍然是平等的。我的意思是例如序列{0,1,22,5,9}和{22,5,9,0,1}应该是相等的。这些序列或重复序列的数量可能是一个大小。我似乎无法想象任何有效的事情（比较每一个新行与所有其他行都需要太多时间），所以我希望有人能提供帮助。提前致谢！

-3热度

1回答

提供生成奇数长度语言的上下文无关语法{w = 0 * 1 *：| w |是奇数}

提供一个上下文无关语法，它可以生成以下语言： Σ= {0,1}：{w = 0 * 1 *：| w |是奇数} 我的解决方案： S-> AB | 0 | 1个 A-> 0A |^ B-> 1B |^ 但是使用这个语法我们可以创建偶数个字符串。欲语法产生L = {0,1,000,111,001,011,00000,11111,00001,00011 ....}

4热度

1回答

如何找到下面代码的时间复杂度？

你能解释一下如何找到下面代码的时间复杂度吗？任何帮助赞赏。 int boo(n) { if (n > 0) { return 1 + boo(n/2) + boo(n/2); } else { return 0; } }

1热度

1回答

记录函数的大O表示

我一直在练习大O表示法，除了递归函数外，我似乎理解它。我可以处理简单的问题（例如，当它是O(n)或O(1)但是其他任何我通常只是迷路了下面是三个练习题，如果有人解释了他们如何找到答案的过程，我会非常感激 public static int method2(int n) { if (n < 1) throw new IllegalArgumentException();

1热度

1回答

在一组矩阵

正如我建模中的R交互网络，我面临以下问题的查找的for循环的复杂性：小号是集合中的所有（n×n个）的正方形的基质如甲使得：在主对角线的甲是0 所有其它的值（即Aij的东坡的所有值CH该我不等于Ĵ）是0或1。如果Aij的 = 1，则味 = 0（但，如果Aij的 = 0，味可以或可能不是0）什么是红衣主教S？我打算编写一个循环遍历所有这些矩阵的程序（S的所有成员）来检查一些属性。我知道复杂性

3热度

3回答

多项式还原是否可逆？

是这种说法真的还是假的：“如果一个问题的是多项式归结为一个问题B，那么B题也必须多项式简化为”。