标签: space-complexity

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

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

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

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

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

public void check_10() {
    for (string i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

这是O(1)还是O(n)？我猜O(n),但不是每次重复使用内存点O(1)？

我在接受采访时得到了以下问题,但找不到解决方案.

给定是一个字符长度为n的数组,并且"重要部分"(必须保存此部分中的所有字符)长度为m,其中n> = m> = 0,如下所示:

如果没有额外的空间,请执行以下过程:
删除所有出现的A并复制所有出现的B,返回变异数组的子数组.例如,对于上面的数组[C,A,X,B,B,F,Q]n = 7,m = 5,输出将是[C,X,B,B,B,B].注意,变异的数组长度是6,因为Q在冗余部分中并且B是重复的.

如果无法执行操作,则返回-1.

例子:

n=2, m=2 , [A,B] => [B,B]  
n=2, m=2 , [B,B] => -1 (since the result [B,B,B,B] is larger then the array)  
n=3, m=2 , [A,B,C] => [B,B]  
n=3, m=3 , [A,B,C] => [B,B,C]  
n=3, m=2 , [Z,B,A] => [Z,B,B] (since A was in the redundant section)

寻找代码示例,这可以在O(n)时间复杂度中完成吗？

当在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

checkIfBalanced()如果树是平衡的,则下面代码中的方法返回true,否则返回false.但是在每次递归中它都会创建TreeData对象.在我看来,空间复杂度是O(1),因为在弹出每个堆栈帧之后,在该堆栈帧上创建的对象的引用将丢失并且垃圾被收集.我对吗 ？

请注意:

1. 我不是在寻找改进/更改代码的建议.下面的代码示例是为了问我的问题而量身定做的.

2. 还有please ignore space-complexity adding stack frames.我正在寻找创建的数字'TreeData'对象的空间复杂性.它在我看来,在任何时候只有3个TreeData对象.这就是我要验证的内容.谢谢.

   private static class TreeData {
        private int height;
        private boolean isBalanced; 

        TreeData(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    public boolean checkIfBalanced() {
        if (root == null) {
            throw new IllegalStateException();
        }
        return checkBalanced(root).isBalanced;
    }

    public TreeData checkBalanced(TreeNode node) {
        if (node == null) return new TreeData(-1, true);

        TreeData tdLeft = checkBalanced(node.left);
        TreeData tdRight = checkBalanced(node.right);

        if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height …

这是Cracking the Coding Interview ^第 5 版的问题9.5

问题:编写一种方法来计算字符串的所有排列

这是我的解决方案,用Java编码(测试它,它工作:))

public static void generatePerm(String s) {
    Queue<Character> poss = new LinkedList<Character>();
    int len = s.length();
    for(int count=0;count<len;count++)
        poss.add(s.charAt(count));
    generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
    if(n==0)
        System.out.println(word);
    else {
        for(int count=0;count<n;count++) {
            char first = possibles.remove();
            generateRecurse(possibles, n-1, word+first);
            possibles.add(first);
        }
    }
}

我同意作者的观点,我的解决方案在O(n!)时间复杂度下运行,因为要解决这个问题,你必须考虑阶乘,就像像"top"这样的单词,第一个字母有三种可能性,2为第二等......

然而,她没有提到空间复杂性.我知道面试官喜欢问你解决方案的时间和空间复杂性.这个解决方案的空间复杂性是什么？

我最初的猜测是O(n ²),因为在每个级别n都有n个递归调用.所以你要加n + n - 1 + n - 2 + n - 3 ..... …

免责声明:关于它有很多问题,但我没有找到任何需要恒定记忆的问题.

汉明数是一个数字2^i*3^j*5^k,其中i,j,k是自然数.

是否有可能在O(N)时间和O(1)(常数)存储器中产生第N个汉明数？在生成下我的意思是完全生成器,即你只能输出结果而不读取先前生成的数字(在这种情况下,内存将不是常量).但是你可以保存一些常数.

我看到只有具有常量内存的最佳算法并不比O(N log N)好,例如,基于优先级队列.但有没有数学证明在O(N)时间内构造算法是不可能的？

python排序采用什么空间复杂度？我无法在任何地方找到任何明确的文件

我正在研究一个Codility问题:

您将获得两个由N个整数组成的非空零索引数组A和B. 数组A和B代表河流中的N种贪婪鱼类,沿着河流向下游排序.

鱼的编号从0到N-1.如果P和Q是两条鱼而P <Q,那么鱼P最初是鱼Q的上游.最初,每条鱼都有一个独特的位置.

鱼数P由A [P]和B [P]表示.数组A包含鱼的大小.它的所有元素都是独特的.数组B包含鱼的方向.它只包含0和/或1,其中:

0表示向上游流动的鱼,1表示向下游流动的鱼.如果两条鱼在相反的方向上移动并且它们之间没有其他(活鱼),它们最终会相遇.然后只有一条鱼可以活着 - 较大的鱼吃较小的鱼.更确切地说,当P <Q,B [P] = 1且B [Q] = 0时,我们说两条鱼P和Q彼此相遇,并且它们之间没有活鱼.他们见面后:

如果A [P]> A [Q]则P吃Q,P仍将向下游流动,如果A [Q]> A [P]则Q吃P,Q仍然会向上游流动.我们假设所有的鱼都以相同的速度流动.也就是说,沿同一方向移动的鱼永远不会相遇.目标是计算将保持活力的鱼的数量.

**Complexity:**

预期的最坏情况时间复杂度是O(N); 预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).

这是我的解决方案:( 100%正确结果)

public int solution(int[] a, int[] b) {
  int remFish = a.length; 
  int i = 0; 
  for (i = 0; i < b.length; i++) {
    if(b[i] != 0){
      /*remFish++; }else { */ break; 
    }
  } 
  Stack<Integer> myQ = new Stack<Integer>(); 
  for (int j = i; j < b.length; j++) { 
    if(b[j] …