问题标签 [space-complexity]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
3 回答
1619 浏览

algorithm - 给定块大小时反转单链表

有一个单连接链表并给出了块大小。例如,如果我的链表是1->2->3->4->5->6->7->8-NULL并且我的块大小是4反转第一个4元素,然后是第二个 4 个元素。问题的输出应该是4->3->2->1->8->7->6->5-NULL

我正在考虑将链表分成大小的段,4然后将其反转。但是这样我就不得不使用很多根本不需要的额外节点。空间复杂度应保持在最低限度。

如果有人能提出一个更好的解决方案,将额外节点的使用保持在最低限度,那将是非常可观的。

0 投票
2 回答
12860 浏览

algorithm - 图灵机中的时间复杂度与空间复杂度

我认为图灵机的时间复杂度和空间复杂度的定义是相同的,我无法区分它们。

请帮我。谢谢。

0 投票
5 回答
7654 浏览

algorithm - 时间复杂度和空间复杂度的关系

时间复杂度为 O( n ) 的算法是否可以具有 O( n2 )或更高的空间复杂度?

0 投票
1 回答
13132 浏览

algorithm - 算法空间复杂度教程

可能重复:
Big O 的简单英文解释

我一直在努力计算我编写的算法的 Big-O 时间和空间复杂度。

任何人都可以指出一个很好的资源来研究更多关于算法的空间复杂度。

编辑:我在这里发布之前搜索了教程。不幸的是,所有的教程都集中在运行时复杂度上,几乎没有写超过几行关于空间复杂度的内容。

0 投票
2 回答
112 浏览

algorithm - 接近大型项目的空间复杂性

我在创业公司被问到这个问题

如果你被要求设计像 Bing Maps 这样的地图,你会如何估计空间复杂度?

对于地图,我能想到的唯一答案是,空间是恒定的,但我不确定我是否朝着正确的方向前进。

如何处理这样的问题?

0 投票
4 回答
3154 浏览

algorithm - 计算 C 函数的空间复杂度?

考虑以下 C 函数:

上述函数的空间复杂度为:

(a) O(1) (b) O(n) (c) O(n!) (d) O(n^n)

我所做的是计算上述代码的递归关系,但我仍然无法解决该递归。我知道这不是与家庭工作相关的网站。但任何帮助将不胜感激。

这是我的复发。

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) +........+ T(1)+ S

其中 S 是某个常数。

0 投票
2 回答
621 浏览

algorithm - 空间中 NxM 和 MxP 矩阵 O(NP) 的矩阵乘法算法?

当两个矩阵相乘时,我们需要分配第三个矩阵来存储结果。在计算算法的内存消耗时是否应该考虑这个分配?

0 投票
2 回答
4458 浏览

algorithm - 是否是原地(就地)命令式快速排序?

快速排序通常被描述为原位(就地)算法,尽管它需要 O(log n) 堆栈空间。那么原位是否意味着“需要少于 O(n) 的额外空间”,或者堆栈空间通常不算作空间复杂度(但为什么会这样呢?),或者 Quicksort 实际上不是原位算法?

0 投票
2 回答
441 浏览

scheme - 方案中 acc 函数的时间复杂度?

我一直在尝试仅针对其中一个参数为该函数找到一个严格的时间复杂度。我以为是 O(p^2) (或者相当大的 theta),但我不确定了。

0 投票
2 回答
1735 浏览

java - 一个很好的排序算法,用于不完全适合内存的大部分排序数据?

如果给你:

  • 一定数量的数据
  • 内存大小为数据大小的一半
  • 部分数据已排序
  • 你不知道排序数据的大小。

你会选择哪种排序算法?我在插入和快速排序之间争论。我知道插入排序的最佳情况是 O(n),但最坏的情况是 O(n 2 )。此外,考虑到内存有限的事实,我会将数据分成两部分,并对它们进行快速排序,然后将所有内容合并在一起。拆分数据需要 O(n) 时间,合并数据需要 O(n) 时间,使用快速排序对数据进行排序需要 O(n log n) 时间,净运行时间为 O(n log n)。

有人对如何改善这一点有任何建议吗?