Tag: 空间复杂度

Bloomfilter实现

使用Bloomfilter，我们将获得空间优化。 cassandra框架还具有Bloom Filter的实现。 但详细地说，这个空间优化是如何实现的？

Arrays.sort（）会增加时间复杂度和时空复杂度吗？

存在与arrays相关的问题，要求时间复杂度为O（n）且空间复杂度为O（1）。 如果我使用Arrays.sort(arr) ，并使用for循环到一个传递循环，例如： public static int hello(int[]A){ Arrays.sort(A); for(int i=0;i<A.length;i++){ ……………….. } return ….; } 因此循环将花费O（n）时间。 我的问题是： Arrays.sort()花费更多时间吗？ 如果我使用Arrays.sort() ，这次复杂性仍然是O（n）吗？ 并且Arrays.sort()花费更多空间吗？

递归斐波那契算法的空间复杂度是多少？

这是Cracking the Coding Interview（第5版）中Fibonacci序列的递归实现 int fibonacci(int i) { if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonaci(i-2); } 在观看关于该算法的时间复杂度的video后， 斐波纳契时间复杂度 ，我现在理解为什么该算法在O（2 n ）中运行。 然而，我正在努力分析空间复杂性。 我在网上看了一下这个问题。 在这个Quora线程中，作者声明“在你的情况下，你有n个堆栈帧f（n），f（n-1），f（n-2），…，f（1）和O（1 ）“。 你不会有2n堆栈帧吗？ 说f（n-2）一帧将用于实际的呼叫f（n-2），但不会有来自f（n-1）的呼叫f（n-2）？

为什么QuickSort使用O（log（n））额外空间？

我已经实现了以下快速排序算法。 在线我已经读过它的空间要求为O（log（n））。 为什么会这样？ 我没有创建任何额外的数据结构。 是因为我的递归会在堆栈上使用一些额外的空间吗？ 如果是这种情况，是否可以通过不使用递归（而是使其迭代）来减少内存？ private static void quickSort (int[] array, int left, int right) { int index = partition(array, left, right); //Sort left half if (left < index – 1) quickSort(array, left, index – 1); //Sort right half if (index < right) quickSort(array, index , right); } private static int partition (int array[], […]