问题标签 [space-complexity]

所以有anxn游戏板，板上的每个位置都有一个整数。玩家一从第 1 行中选择一个数字，玩家 2 从第 2 行中选择一个数字，他们交替进行直到没有更多行。然后他们将所有数字相加，如果总和等于预定的总和 S，则玩家 1 获胜，否则玩家 2 获胜。对于特定棋盘和总和（B，S），玩家 1 的获胜策略是无论玩家 2 做什么，玩家 1 都能获胜。我想证明这个问题是 PSpace-complete

所以首先我必须证明它在 PSpace 中，我认为这很容易，因为移动的总数受棋盘大小的限制，即 n^2。

我一直坚持证明它很难 PSpace，但我知道我必须从 QSAT 中减少，但我不知道如何。有人可以帮忙吗？

编辑：其实我不知道我必须从 QSAT 中减少，但是在搜索之后似乎 QSAT 是最有可能的候选人。许多其他两人游戏，地理是最突出的例子，从 QSAT 减少，所以我认为这也是必须的。但是，如果我对此有误，请随时纠正我。

这个问题对我来说看起来很简单，但只是想看看我是否朝着正确的方向前进。

是不是说当n=1那么简单？？

我们以这种合并排序的实现为例

a) 这种归并排序的时间复杂度是O(n lg(n))。并行化（1）和（2）会带来任何实际收益吗？从理论上讲，似乎在将它们并行化之后，您最终也会进入O(n lg(n)). 但实际上我们能获得任何收益吗？

b) 这里合并排序的空间复杂度是O(n)。但是，如果我选择使用链表执行就地合并排序（不确定是否可以合理地使用数组完成），空间复杂度是否会变为O(lg(n))，因为您必须考虑递归堆栈帧的大小？我们可以将O(lg(n))其视为常数，因为它不能超过 64 吗？我可能在几个地方误解了这一点。64到底有什么意义？

c)比较排序算法 - Cprogramming.com说合并排序需要使用链表的恒定空间。如何？他们对待O(lg(n))恒定吗？

d)添加以获得更清晰。对于空间复杂度计算，假设输入数组或列表已经在内存中是否公平？当我进行复杂性计算时，我总是计算除了输入已经占用的空间之外我需要的“额外”空间。否则空间复杂度将永远是O(n)或者更糟。

插入 n 个元素后，跳过列表使用的预期空间是多少？

我预计在最坏的情况下，空间消耗可能会无限增长。

维基百科说“空间 O(n)”。

如何以一种或另一种方式证明这一点？

下面是两个片段。请注意程序之间的唯一区别是一个break to return和另一个return立即。我知道在方法中设置一个退出点是一种很好的设计实践。但我不担心这里的设计。如果我为使用支付额外费用，我需要支付break多少额外的计算/内存/时钟周期？

方案一：

方案二：

我在一次采访中被问到，解决检查回文问题的有效方法。

现在我可以做两件事：

1. 从 i = 0 到 i = n/2 并比较第 i 个和第 n 个字符是否相等。
2. 我可以使用递归来检查第一个和最后一个是否相同，并且字符串的其余部分是一个回文。

第二个是递归的。我的问题是算法的递归和非递归版本的空间复杂度有什么区别？

给定一个大小为 nxm 的矩阵，其中填充了 0 和 1

例如：

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

如果矩阵在 (i,j) 处为 1，则用 1 填充第 j 列和第 i 行

即，我们得到：

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

所需复杂度：O(n*m) 时间和 O(1) 空间

注意：您不能在矩阵条目中存储除“0”或“1”之外的任何内容

以上是微软面试题。

我想了两个小时。我有一些线索，但不能再继续了。

行。这个问题的第一个重要部分是Even using a straight forward brute-force way，它不容易解决。

如果我只使用两个循环遍历矩阵中的每个单元格，并更改相应的行和列，则无法完成，因为生成的矩阵应基于原点矩阵。

例如，如果我看到a[0][0] == 1，我不能全部更改为row 0，因为那会影响as本来没有 0。column 01row 1row 1

我注意到的第二件事是，如果一行r只包含0而一列c只包含0，那么a[r][c]一定是0；对于不在此模式中的任何其他位置应该是1。

然后另一个问题来了，如果我找到这样的行和列，我怎样才能将相应的单元格标记a[r][c]为special它已经是 0。

我的直觉是我应该对此使用某种位操作。或者为了满足所需的复杂性，我必须做类似After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column.

即使对于不考虑时间复杂度的蛮力，我也无法用其他条件解决它。

有人有线索吗？

解决方案：Java版

@japreiss 已经回答了这个问题，他/她的回答是聪明而正确的。他的代码是 Python 的，现在我给出 Java 版本。学分都去@japreiss

这让我有点困惑。当约束如下时，我解决给定问题的方法应该是什么：

1）不使用额外空间：例如：如果我想对给定的数组进行排序，我几乎没有办法做到这一点。冒泡排序，不断交换（只是循环，没有递归）。我相信据说这是不使用额外空间的。如果我使用递归对元素进行排序，会发生什么情况。是和“不使用额外空间”一样，还是使用的堆栈计入算法的空间复杂度？

2）在O(1)空间中：O(1)空间是什么意思？这是否意味着恒定的空间。现在如果它是常数空间，那么请评论以下情况：

a）如果我在第三个变量的帮助下交换冒泡排序。它不是一个额外的空间，它不会依赖于输入的大小，所以它是恒定的空间。

b）此外，如果我对自然数应用计数排序，它实际上并不需要与总数成比例的空间量，我们是否认为它在恒定空间 O(1) 中。

如果有区别，请解释一下。谢谢

在我得到答案之前，我冒着这个问题被关闭的风险，但我真的很想知道答案。所以这里。

我目前正在尝试学习算法，并且我开始理解它，但无法与之相关。

我了解时间复杂性和空间复杂性。我也确实了解一些基于伪代码的排序算法

排序算法如

1. 冒泡排序
2. 插入排序
3. 选择排序
4. 快速排序
5. 合并排序
6. 堆排序（一些什么）

我也知道最好的情况和最坏的情况（平均情况不是很多）。

一些网上相关的参考资料

• 以图形方式显示以上所有内容的好地方。
• 这也让我有了很好的理解。

但我的问题是 - 有人可以给我实现这些排序算法的真实世界示例。

我只想知道，什么时候后缀树优于增强的后缀数组。

在阅读了用增强的后缀数组替换后缀树之后，我看不到使用后缀树的理由了。有些方法可能会变得复杂，但是您可以使用后缀数组来做所有事情，您可以使用后缀树来做任何事情，并且您需要相同的时间复杂度但更少的内存。

一项调查甚至表明，后缀数组更快，因为它们对缓存更友好，并且不会产生尽可能多的缓存未命中，然后是后缀树（因此缓存可以更好地预测数组使用情况，然后是递归树结构）。

那么，有谁知道选择后缀树而不是后缀数组的原因？

编辑 好的，如果您知道更多，请告诉我，到目前为止：

• 后缀数组不允许在线构建
• 一些模式匹配算法在后缀树上运行得更快
• （补充）由于在线构建，您可以将其保存在 hd a 并扩大现有的后缀树。如果您使用 SSD，它也应该很快安静。