我们能否在O(n*n)以下的时间复杂度内进行计算？（使用nlogn或n的时间复杂度）
这是一个非常著名的跨国公司问我的问题。问题如下... 输入一个由0和1组成的二维N*N数组。如果A(i,j) = 1，则与第i行和第j列对应的所有值都将变为1。如果已经有一个1，则它仍然保持为1。 例如，如果我们有以下数组： 1 0 0 0 0 0 1 1 0 0 0 0...
C++ string类erase成员函数的时间和空间复杂度
我想知道是否有人了解C++的string::erase函数的实现方式及其复杂度。我知道C++ string是字符对象。我假设它不会分配和创建一个新的字符对象，然后从旧字符串中复制字符O(n)次并占用O(n)空间。它会将字符向左移动O(n)次且仅在O(1)空间中吗？我在cplusplus.com...
在数组中查找连续的范围
你有一个整数数组，需要输出包含数组中所有数字的最大区间。这些数字可以按任意顺序出现。例如，假设给定的数组为：{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15} 我们在这里找到了两个（非平凡的）范围，这些范围中所有的整数都出现在数组中，即 [2,8] 和 [10,12]。...
头部反转与尾部反转的空间复杂度对比
在许多系统中，head.reverse 需要与列表大小成比例的空间，而 last 则只需要常量空间。是否有系统可以执行这样的转换? 对于 reverse.take n.reverse 也是如此吗? 编辑: 我想扩展我的问题: 我不追求具体的转换，我只是想达到任何优化的目的。
在使用“少量”额外空间的情况下，在列表中找到k个不重复的元素。
原始问题陈述如下： 给定一个32位无符号整数数组，其中每个数字都出现两次，除了其中三个数字只出现一次。在O(n)时间内使用O(1)额外空间找到这三个数字。输入数组是只读的。如果有k个例外情况而不是3个呢？ 如果您接受由于输入限制（数组最多可以有2^33个条目）而导致非常高的常数因子，则可以...
为什么基数排序的空间复杂度为O(k + n)？
考虑一个由n个数字组成的数组，最大有k位数（参见Edit）。考虑来自这里的基数排序程序：def radixsort( aList ): RADIX = 10 maxLength = False tmp, placement = -1, 1 while not maxLengt...
在范围（1，2）内的三元组之和
给定一个包含 n 个正实数的数组，查找其中是否存在一个三元组，使得这个三元组的和位于 (1, 2) 的区间内。要求用线性时间和常数空间完成。 该数组未排序。 数字都是正数。 数字为实数。 感谢您的任何帮助。
这是一个问题标题： 快速排序算法是否是原地排序？
快速排序通常被描述为一种就地（in-place）算法，尽管它需要O(log n)的堆栈空间。那么，就地是指“需要少于O(n)的额外空间”，还是堆栈空间通常不计入空间复杂度（但为什么会这样呢？），或者说快速排序实际上不是一种就地算法？
深度优先搜索的时间/空间复杂度
我查看了其他一些StackOverflow答案，它们与我的讲师在他的幻灯片中写的不同。 深度优先搜索的时间复杂度为O(b^m)，其中b是搜索树的最大分支因子，m是状态空间的最大深度。如果m远大于d，则效率很低，但如果搜索树“多叉”，则可能比广度优先搜索快得多。 他接着说.. ...