标签: space-complexity

给定n数组中的正实数,找出该集合中是否存在三元组,使得三元组的总和在该范围内(1, 2).在线性时间和恒定空间中进行.

• 该数组未订购.
• 数字是积极的
• 数字是实数

任何帮助将不胜感激.谢谢.

我已经实现了以下快速排序算法.在线我已经读过它的空间要求为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[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on …

最初的问题陈述是这样的:

给定一个32位无符号整数数组,其中每个数字除了其中三个(恰好只出现一次)之外恰好出现两次,使用O(1)额外空格在O(n)时间内找到这三个数字.输入数组是只读的.如果有k个例外而不是3个怎么办？

如果由于输入限制(阵列最多可以包含2 ³³个条目)而接受非常高的常数因子,则很容易在?(1)时间和?(1)空间上解决这个问题:

for i in lst:
    if sum(1 for j in lst if i == j) == 1:
        print i

因此,为了这个问题,让我们放弃比特长度的限制,并专注于数字可以达到m比特的更普遍的问题.

推广k = 2的算法,我想到的是以下内容:

1. 对具有最低有效位的那些数字1和具有0单独的那些数字进行异或.如果对于两个分区,结果值不为零,我们知道我们已将非重复数字划分为两个组,每个组至少有一个成员
2. 对于每个组,尝试通过检查第二个最低有效位等进一步对其进行分区

不过,有一个特殊情况需要考虑.如果在对一个组进行分区后,其中一个组的XOR值都为零,我们不知道其中一个结果子组是否为空.在这种情况下,我的算法只是将该位丢弃并继续下一个,这是不正确的,例如它输入失败[0,1,2,3,4,5,6].

现在我的想法是不仅要计算元素的XOR,还要计算应用某个函数后的值的异或(我在f(x) = 3x + 1这里选择).有关此附加检查的反例,请参阅下面的Evgeny的答案.

现在虽然以下算法对于k> = 7是不正确的,但我仍然在这里包含实现以给你一个想法:

def xor(seq):
  return reduce(lambda x, y: x ^ y, seq, 0)

def compute_xors(ary, mask, bits):
  a = xor(i for i in ary if i …

鉴于以下功能:

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

我知道Big O时间复杂度是O(2^N)因为每次调用都会调用该函数两次.

我不明白为什么空间/内存的复杂性是O(N)什么？

我们以Merge Sort的这个实现为例

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);  ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a)此合并排序的时间复杂度为O(nlg(n)).并行化(1)和(2)会带来任何实际收益吗？从理论上讲,似乎在并行化后,你最终会得到O(nlg(n).但实际上我们可以获得任何收益吗？

b)此合并排序的空间复杂度为O(n).但是,如果我选择使用链接列表执行就地合并排序(不确定是否可以合理地使用数组),空间复杂度将变为O(lg(n)),因为您必须考虑递归堆栈帧大小？我们可以将O(lg(n))视为常数,因为它不能超过64吗？我可能在几个地方误解了这一点.64的意义究竟是什么？

c)http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html说合并排序需要使用链表的恒定空间.怎么样 ？他们对待O(lg(n)不变？

d)[添加以获得更多清晰度]对于空间复杂度计算,假设输入数组或列表已经在内存中是公平的吗？当我进行复杂度计算时,我总是计算除了已经输入的空间之外我将需要的"额外"空间.否则空间复杂性将始终为O(n)或更差.

我在一次训练中遇到了这个问题.即我们给出了N不同的值(N<= 100).让我们命名这个数组A[N],这个数组A,我们确信,我们有数组1 A[i]≤10 ⁹.其次,我们已经给数S ,其中S≤10 ⁹.

现在我们必须用这个值来解决经典硬币问题.实际上我们需要找到最小数量的元素,它们将完全相加S.每个元素A都可以无限次使用.

• 时间限制:1秒

• 内存限制:256 MB

例:

S = 1000, N = 10

A[] = {1,12,123,4,5,678,7,8,9,10}. The result is 10.

1000 = 678 + 123 + 123 + 12 + 12 + 12 + 12 + 12 + 12 + 4

我试过了什么

我试图用经典的动态编程硬币问题技术来解决这个问题,但是它使用了太多内存并且超出了内存限制.

我无法弄清楚我们应该保留这些价值观.提前致谢.

以下是经典dp硬币问题无法解决的几个测试用例.

S = 1000000000 N = 100

1 373241370 973754081 826685384 491500595 765099032 823328348 462385937 
251930295 …

我一直在谷歌搜索过去2个小时,我找不到PHP内置函数时间和空间复杂性的列表.我有isAnagramOfPalindrome问题要解决以下最大允许的复杂性:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

其中N是输入字符串长度.这是我最简单的解决方案,但我不知道它是否在复杂性限制范围内.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it
    static public function isAnagramOfPalindrome($S) {

        // here I am counting how many characters have odd number of occurrences
        $odds = count(array_filter(count_chars($S, 1), function($var) {
            return($var & 1);
        }));
        // If the string length is odd, then a palindrome …

我很难理解什么是O(1)空间复杂性.据我所知,这意味着算法所需的空间不会随着输入或我们使用算法的数据大小而增长.但它究竟意味着什么？

如果我们在链表上使用算法说1-> 2-> 3-> 4,要遍历列表以达到"3",我们声明一个临时指针.并遍历列表直到我们达到3.这是否意味着我们仍然有O(1)额外的空间？或者它意味着完全不同的东西.如果这根本没有意义,我很抱歉.我有点困惑.

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑 好的,如果你知道更多告诉我,到目前为止:

• 后缀不允许在线构造
• 一些模式匹配算法在Suffixtrees上运行得更快
• (补充)由于在线构造,你可以将它保存在高清上并扩大现有的后缀树.如果你使用SSD,它也应该安静快速.

这是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);
}

在观看关于该算法的时间复杂度的视频后,斐波纳契时间复杂度,我现在理解为什么该算法在O(2 ⁿ)中运行.然而,我正在努力分析空间复杂性.

我在网上看了一下这个问题.

在这个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)？