问题标签 [space-complexity]

以下代码必须根据给定的字典从字符串（没有空格）中识别单独的单词。它尝试在每个字符之后放置一个空格，并检查到目前为止该单词是否在字典中，然后尝试形成一个新单词。如果新词不成功，它会尝试扩展前一个词。你如何计算这样一个程序的内存复杂度？它是指数/阶乘吗？记忆化对复杂性有什么影响吗？（假设如果单词在字典中以恒定时间出现，则 is_word() 返回）

我只是想检查一下我对 Russell 和 Norvig 给出的算法和计算的理解是否正确。

我使用传教士和食人族作为一个问题来测试时间和空间的复杂性。计算深度并不是什么大问题。我总是在深度 11 找到解决方案。我无法理解的是分支因素。

罗素和诺维格第 82 页说：

O(b^(d-1))“探索集中会有节点O(b^d)，边境会有节点……”

我的程序显示8502探索集中的14006节点和前沿节点。

d这是我的思考过程的方式：如果我根据 Russell 和 Norvig取节点数并取根，我应该得到分支因子是什么。现在我不知道我的想法是否正确。我刚想出来。

所以我取 10 个 (d-1) 的根8502并得到2.47（大约），我取 11 个 (d) 的根14006并得到2.39（大约）。所以我的结论是分支因子 b 大致为2.43。

我是完全达到目标还是完全错了？这是我现在正在做的事情之一。但很想知道我是对还是错。

考虑以下 C 函数：

上述函数的空间复杂度为

根据我的说法，在上述问题中，答案应该是（2），但答案是（3）选项。虽然它是递归函数，但堆栈永远不会超过 O(n) 堆栈深度。谁能解释我为什么是这个答案（3），我在哪里想错了？

我很难找出一种算法来对时间复杂度为 O(nlgn) 且空间复杂度为 O(1) 的单链表进行排序。

对于时间复杂度问题，我尝试过使用归并排序，但似乎我的递归解决方案可能存在空间复杂度问题。

我已经阅读并发现使用递归是不可能的。这是真的？

有人可以提供一些粗略的伪代码或用 Java 来回答这个问题吗？

我正在阅读“Cracking the Coding Interview”一书，遇到了一个问题“编写一个程序以按升序对堆栈进行排序。您可以使用额外的堆栈来保存项目，但您不能将元素复制到任何其他数据结构中（如数组）。栈支持以下操作：push、pop、peek、isEmpty。

这本书给出了 O(n^2) 时间复杂度和 O(n) 空间的答案。

但是，我遇到了这个博客，它使用快速排序方法提供了 O(n log n) 时间复杂度的答案。

我想知道的是空间复杂度 O(n^2) 吗？由于对该方法的每次调用都涉及初始化另外两个堆栈，以及另外两个递归调用。

我对空间复杂性仍然有点动摇。我不确定这是否是 O(n^2) 空间，每个递归调用产生的新堆栈小于上一级的堆栈。

如果有人可以在他们的答案背后给出一点解释，那就太好了。

我总是在评估问题的复杂性时遇到问题。我通常会尝试找到一个 O(n) 解决方案，但有时 O(nlogn) 甚至 O(n^2) 是最好的解决方案。

我知道的一个“经验法则”是，如果你有一个排序数组并且你需要找到一些东西，它可能可以在 O(logn) 中完成。我也知道排序不能比 O(nlogn) 更快。没有经验的程序员可以遵循任何类似的规则吗？你知道反复出现的问题的复杂性吗？

对我来说最麻烦的是 O(n^2)，尤其是当我面临考试压力并且我浪费时间去寻找更好的考试时。

我希望这不是一个过于宽泛和基于意见的问题。

谢谢！

我一直在阅读有关哈希表、字典等的内容。我看过的所有文献和视频都暗示哈希表具有空间/时间权衡属性。

我很难理解为什么哈希表比具有相同数量的总元素（值）的数组或列表占用更多空间？它与实际存储散列键有关吗？

据我所知，在基本术语中，哈希表需要一个键标识符（比如一些字符串），通过一些哈希函数传递它，该函数会输出一个数组或其他数据结构的索引。除了将对象（值）存储在数组或表中的明显内存使用之外，为什么哈希表会占用更多空间？我觉得我错过了一些明显的东西......

有一个数组相关的问题，要求时间复杂度为O(n)，空间复杂度为O(1)。

如果我使用Arrays.sort(arr), 并使用一个for循环到一个循环循环，例如：

}

所以循环将花费 O(n) 时间。我的问题是：会Arrays.sort()花费更多时间吗？如果我使用Arrays.sort()，这个时间复杂度仍然是 O(n) 吗？并且会Arrays.sort()花费更多空间吗？

想要检查上面简单代码的空间复杂度以消除重复。

1. 存储在集合中 -> O(n)
2. 由于 set.toArray - O(n) 生成的数组中的存储
3. 存储在新创建的列表中 - O(n)

总 O(3n) 与 O(n) 相同。

你能帮我确认一下吗？

该算法用于逐级打印常见的二叉树。

和 的时间复杂度和空间复杂度是printSpecificLevel_BT()多少printBT_LBL()？

我认为printSpecificLevel_BT时间复杂度是O(lg N)，空间复杂度是O(lg N)。
我认为printBT_LBL()时间复杂度是O((lgN)^2)，空间复杂度是O((lgN)^2)。

这个对吗？