标签: space-complexity

Quicksort通常被描述为原位(就地)算法,尽管它需要O(log n)堆栈空间.所以,做原地意味着"需要小于O(n)的额外空间",还是栈空间一般不能算作空间复杂度(但为什么会这样呢？),或者是快速排序实际上不是原地算法？

假设n条记录的密钥范围为1到k.

• 编写一个算法,在O(n + k)时间内对记录进行排序.
• 您可以在输入数组外使用O(k)存储.
• 你的算法稳定吗？

如果我们使用计数排序,我们可以在O(n + k)时间内完成并且稳定但不适用.
如果k = 2,它可以在适当的位置完成,但它不稳定(使用两个变量来维持数组中的索引k = 0和k = 1)
但是对于k> 2,我想不出任何好的算法

这是一个面试问题.

我得到了一系列n+1来自该范围的整数[1,n].数组的属性是它有k (k>=1)重复,每个副本可以出现两次以上.任务是找到在尽可能最佳的时间和空间复杂度下不止一次出现的数组元素.

在经历了重大的挣扎之后,我自豪地想出了O(nlogn)一个占据O(1)空间的解决方案.我的想法是将范围[1,n-1]分成两半,并确定两半中的哪一半包含来自输​​入数组的更多元素(我使用的是Pigeonhole原理).该算法递归地继续,直到它达到发生两次的间隔[X,X],X这是重复的.

面试官很满意,但后来他告诉我存在O(n)恒定空间的解决方案.他慷慨地提供了一些提示(与排列相关的东西？),但我不知道如何提出这样的解决方案.假设他没有说谎,有人可以提供指导吗？我搜索了SO,发现这个问题很少(更容易)变化,但不是这个特定的.谢谢.

编辑:为了使事情变得更复杂,采访者提到不应该修改输入数组.

对于Lempel-Ziv-Welch和Huffman压缩算法,Big O表示法的空间和时间复杂性有哪些？谷歌让我失望.

谢谢,

弗朗西斯科

我不擅长确定时间和记忆的复杂性,如果有人可以帮助我,我会很感激.

我有一个算法,在这里,我不知道它的时间和记忆复杂性是什么.

Function sample(k)
   IF k < 2
       Return 0
   Return 1 + sample(k/2)

它的时间和内存复杂性是什么？为什么？

谢谢

我查看了其他各种StackOverflow答案,它们都与我的讲师在幻灯片中写的不同.

深度优先搜索的时间复杂度为O(b ^ m),其中b是搜索树的最大分支因子,m是状态空间的最大深度.如果m比d大得多,但是如果搜索树是"浓密的",则可能比广度优先搜索快得多.

他继续说..

空间复杂度为O(bm),即动作序列长度的空间线性!只需存储从根节点到叶节点的单个路径,以及路径上每个节点的剩余未扩展兄弟节点.

StackOverflow的另一个答案表明它是O(n + m).

删除二叉树中所有节点的标准算法使用沿这些行的节点上的后序遍历:

if (root is not null) {
   recursively delete left subtree
   recursively delete right subtree
   delete root
}

该算法使用O(h)辅助存储空间,其中h是树的高度,因为在递归调用期间存储堆栈帧所需的空间.但是,它在时间O(n)中运行,因为每个节点只访问一次.

是否有算法仅使用O(1)辅助存储空间删除二叉树中的所有节点而不牺牲运行时间？

f (int n){
    if (n<=0){
        return 1;
    }
    return f(n-1) + f(n-1);
}

假设我们做了f(4).我的想法是它会是O(2 ^ n),从那以后为了找到f(n-1)+ f(n-1),我们必须将f(n-1)= f(3)推到调用堆栈两次,然后f(2)调用堆栈的四倍等.但是,我得到的这本书说是O(n).为什么这是真的？

在许多系统中,head.reverse需要与列表大小成比例的空间,而last需要恒定的空间.

有没有系统来进行这样的转变？同样的reverse.take n.reverse？

编辑:我想扩展我的问题:我不是在经历了一次具体的转变 - 我宁愿在此之后进行任何优化.

考虑一个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 …