标签: space-complexity

考虑一个n数字具有最大k数字的数组(请参阅编辑).从这里考虑基数排序程序:

def radixsort( aList ):
  RADIX = 10
  maxLength = False
  tmp, placement = -1, 1

  while not maxLength:
    maxLength = True
    # declare and initialize buckets
    buckets = [list() for _ in range( RADIX )]

    # split aList between lists
    for  i in aList:
      tmp = i / placement
      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False

    # empty lists into aList array
    a = 0
    for …

这是一个非常着名的跨国公司向我询问的问题.问题如下......

输入0和1的2D N*N数组.如果A(i,j)= 1,则对应于第i行和第j列的所有值将为1.如果已经存在1,则它保持为1.

举个例子,如果我们有数组

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

我们应该得到输出

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

输入矩阵是稀疏填充的.

这可能小于O(N ^ 2)吗？

没有提供额外的空间是另一个条件.我想知道是否有办法使用空间<= O(N)来实现复杂性.

PS:我不需要给出O(N*N)复杂度的答案.这不是一个家庭作业问题.我已经尝试了很多,无法得到一个正确的解决方案,并认为我可以在这里得到一些想法.抛弃印刷的复杂性

我的粗略想法是可以动态地消除遍历的元素数量,将它们限制在2N左右.但我无法得到一个正确的想法.

假设我有大小为 N（即 N 个元素）的数据，并且字典是用容量 N 创建的。以下的复杂性是多少：

• 整个字典的空间
• time -- 将条目添加到字典中

MS 仅显示条目检索接近 O(1)。但其余的呢？

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

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

任何人都可以指出一个很好的资源来研究算法的空间复杂性.

编辑:我在发布之前搜索过教程.遗憾的是,所有教程都侧重于运行时复杂性,并且几乎没有写太多关于空间复杂性的内容.

这是我学校过去一年中期论文的问题.下面附有一张图,用于显示机器人如何从同一张纸上移动.我的担忧在橙色部分中说明.

基本上,只要机器人遇到左侧未看到的网格方块,机器人就会向前移动并向左转.

给予机器人横向3号网格的指令序列是:('F','T','F','T','F','F','T','F',' F','T','F','F','F')其中'F'表示向前移动一个方格,'T'表示向左转90度.请注意,最后一条指令会导致机器人退出网格.函数gen_seq将网格的大小作为输入,并返回机器人横向网格的指令序列.指令序列是一个包含字符串'F'和'T'的元组,它们代表forward和turn命令.

提供函数gen_seq的递归或迭代实现.提示:Recall int可以与元组相乘.

说明实施时间和空间的增长顺序,并解释您的答案.

这些是markscheme中建议的答案.

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (n-1)*('F',)
        seq += side + side + ('F',)
    return seq

时间:O(n ^ 3).在每个函数调用(递归)或循环(迭代)中,创建螺旋的每个"层"的路径长度的新元组.由于螺旋的长度是n ^ 2,并且有n个函数调用或循环运行n次,因此总时间是n ^ 2*n = O(n3).换句话说,它是平方和:1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ::: + …

我想知道是否有人知道 C++ string::erase 函数的实现及其复杂性。我知道 C++ 字符串是一个字符对象。我假设它不会分配和创建一个新的字符对象，然后从旧字符串 O(n) 和 O(n) 空间复制字符。它是否在字符 O(n) 和 O(1) 空间上移动？我查看了 cplusplus.com 和 Bjarne Stroustrup 的书，但没有找到答案。有人可以指出我实现它的源代码或知道答案吗？

谢谢！

我正在写一篇关于 Pythonlist.clear()方法的博文，其中我还想提到底层算法的时间和空间复杂度。我预计时间复杂度为O(N)，迭代元素并释放内存？但是，我发现一篇文章提到它实际上是一个O(1)操作。然后，我在 CPython 实现中搜索了该方法的源代码，找到了一个我认为是 的实际内部实现的方法list.clear()，但是，我不确定它是。下面是该方法的源代码：

static int
_list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
         /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
           Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there …

数学" CylindricalDecomposition实现称为圆柱代数分解的算法.Wolfram MathWorld关于圆柱代数分解的文章称,这种算法"在计算上对于复杂的不等式变得不可行".

这句话可以更精确吗？具体来说,时间和空间如何与多元多项式的变量的次数和数量相关？时间和空间是否依赖于其他参数？

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

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

据我了解，用基本术语来说，哈希表采用一个键标识符（例如某个字符串），将其传递给某个哈希函数，该函数会生成数组或其他数据结构的索引。除了在数组或表中存储对象（值）时明显使用内存之外，为什么哈希表会占用更多空间？我觉得我错过了一些明显的东西......

当在Python中反转列表时，我通常使用数组[::-1]进行反转，并且我知道更常见的方法可能是从列表的两侧进行交换。但我不确定这两种解决方案之间的区别，例如时间复杂度和空间复杂度。

这两种方法的代码如下：

def reverse(array):
    array[:] = array[::-1]


def reverse(array):
    start, end = 0, len(array)-1
    while start < end:
        array[start], array[end] = array[end], array[start]
        start += 1
        end -= 1