标签: asymptotic-complexity

我试图使用递归树来解决给定的递归, T(n) = 3T(n/3) + n/lg n.

在第一级(n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

事实证明,在第二级n/(log(n/9)).

我可以用以下的形式概括上述等式 n.loglogn

这是一个普遍的疑问,我需要对此有所了解.

注意:必须Theta(n^k log^k (n))在该函数k中的任何函数都应> = 1.在这种情况下,k为-1,因此主定理不会进入图像

我是第一次通过算法类的分析,并想知道是否有人可以协助下面的例子.我相信我已经解决了它的O(n)复杂性,但是想知道是否有更好的版本,我没有想到O(logn)？

设A = A [1] <= ... <= A [n + 1]是n个不同整数的排序数组,其中每个整数的范围为[1 ... n + 1].也就是说,A中缺少{1,...,n + 1}中的一个整数.描述一个efficeint算法来找到缺失的整数.分析算法的最坏情况复杂性(对数组A的访问次数).

我所拥有的解决方案相对简单,我相信在最坏的情况下会导致N的复杂性.也许我在想这个例子,但有更好的解决方案吗？

我的解决方案

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

这背后的逻辑是因为它被排序,第一个元素必须是1,第二个必须是2,依此类推,直到数组中的元素大于它应该是的元素,指示一个元素错过了,返回应该是的元素,我们有失踪的元素.

这是正确的逻辑吗？还有更好的方法吗？

感谢您的阅读并提前感谢您的帮助.

我试图通过一本书来理解Big-O符号,它通过使用函数来覆盖Big-O,尽管我有点困惑.书中说O(g(n))其中g(n)是f(n)的上界.所以我理解这意味着g(n)给出了较大n值时f(n)的最大增长率.

并且存在n_0,其中cg(n)的生长速率(其中c是某些常数)和f(n)具有相同的生长速率.

但令我困惑的是这些关于在数学函数中找到Big O的例子.

这本书说找到f(n)= n ^ 4 + 100n ^ 2 + 50的上界然后他们说n ^ 4 + 100n ^ 2 + 50 <= 2n ^ 4(不知道为什么2n ^ 4)然后他们一些如何找到n_0 = 11和c = 2,我理解为什么大O是O(n ^ 4),但我只是对其余的感到困惑.

这是令人沮丧的,因为我不明白,但我觉得这是一个我必须理解的重要话题.

如果有人好奇的话,那本书就是Narasimha Karumanchi的数据结构和算法

不确定这篇文章是属于这里还是属于数学板.

为什么声明:

算法A的运行时间至少为O(n²)

没意义？

插入排序算法的运行时间最多为O(n²)

这是对的吗？

我尝试了网但无法得到很好的解释.

我有另一个问题:

我知道任何线性函数a⋅n+ b都是O(n),也是O(n²).它也是O(n³)吗？

注意:这是Cracking the Coding Interview 5th Edition的问题4.3

问题:给定排序(递增顺序)数组,编写算法以创建具有最小高度的二叉搜索树

这是我的算法,用Java编写来解决这个问题

  public static IntTreeNode createBST(int[] array) {
         return createBST(array, 0, array.length-1);
   }
   private static IntTreeNode createBST(int[] array, int left, int right) {
        if(right >= left) {
            int middle = array[(left + right)/2;
            IntTreeNode root = new IntTreeNode(middle);
            root.left = createBST(array, left, middle - 1);
           root.right = createBST(array, middle + 1, right);
            return root;
         } else {
             return null;
         }
    }

我对作者的代码检查了这个代码,它几乎相同.
但是,我很难分析此算法的时间复杂度.
我知道这不会像二进制搜索一样在O(logn)中运行,因为你没有在每个递归级别做同样的工作量.EG在第一级,1个工作单元,第2级 - 2个工作单元,第3级 - 4个工作单元,一直记录 …

我发现关于渐近复杂性存在很多争议List.Add().我怀疑它的来源是最糟糕的情况导致底层数组调整大小并且逻辑上是O(n)操作.但是,每次列表空间不足时,阵列的大小会增加两倍.这使n元素所需的调整大小成比例log(n).

这是不是意味着Add平均情况下操作的渐近复杂性会是O(n/log(n))什么？

真正的基准List.Add()是在下面.然而,基准测试并不能真正表达这种操作 - 在任何偏离直线(对数刻度)线变得可见之前,我们可能会耗尽内存.

是否有编程方式或eclipse插件来计算java方法的big-O表示法？

我必须完成实习的在线编程测试,并得到关于复杂性分析的问题.我回答了这个问题并且标记错了,我只想理解为什么,所以我可以改进.

问题:

当reverseOrder为true且为false时,给出以下算法的复杂性:

List<int> stackToList(Stack<int> stack, bool reverseOrder) {
    List<int> items = new List<int>();

    while (stack.Count > 0) {
        int item = stack.Pop();

        if (reverseOrder) {
            items.Insert(0, item);
        } else {
            items.Add(item);
        }
    }

    return items;
}

编辑:这是多项选择,可能的答案是:

• O(1)
• O(nlogn)
• 上)
• 为O(n ^ 2)

您可以在reverseOrder为true时选择一个,为false时选择另一个.

我的答案:

• 当reverseOrder为真时:O(n ²)
• 当reverseOrder为false时:O(n ²)

我通过以下方式得到了这个答案:

• while循环将迭代n次数,因为它会继续,直到没有剩余的元素弹出
• Pop() 是 O(1)

• 在的情况下reverseOrder存在true,一个Insert到该列表的前面制成.由于List<T>是由数组支持,它被动态地调整大小和每一个元件向上移动一个空间,所述元件被插入在索引0.根据https://msdn.microsoft.com/en-us/library/sey5k5z4(v = vs.110).aspx:

  该方法是O(n)操作,其中n是Count.

• 在的情况下reverseOrder存在false …

我确定一个数字是否为素数的原始函数是:

bool is_prime(int x) {
    for (int y = 2; y < x; ++y) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

这很复杂,O(x)因为你可能不得不去x.

我已经了解了一些优化,需要检查我的big-o.这是改进的计划:

bool is_prime(int x)
{   
    if (x % 2  == 0 && x > 2) {
        return false;
    }
    for (int y = 3; y*y <= x; y += 2) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

事实上我现在正在 …

为什么时间复杂度为O(1)pow(x,y)而O(n)为x ** y？

在这里查看来自agf的 评论