标签: asymptotic-complexity

我正在学习算法课程,在那里我看到计数排序的时间复杂度是O(n + k),其中k是数字范围,n是输入大小.我的问题是,当k和n之间的差异太大时,例如当k = O(n ²)或O(n ³)时,我们可以说复杂度是O(n ²)或O(n ³) ？然后在这种情况下计数排序不是一个明智的方法,我们可以使用合并排序.我对吗？

给定一个数组,对于每个元素,我需要找到给定元素右边的最大元素,该元素大于当前元素.

数学上,对于i数组中的每个索引A,我需要找到j这样的索引

A[j] > A[i]
j > i
A[j] - A[i] is minimum

我需要找到j每个索引i

蛮力解决方案将是O(n^2),我希望做得更好.我认为O(n log n)使用自平衡BST可以实现解决方案,但这似乎相当复杂.而且我需要一个O(n)解决方案.

有O(n)这个问题的解决方案吗？是否有证据表明下限是 O(n log n)？

如果我们有两个大小为n的数组并且想要对它们的和进行排序,那么天真的方法是将它们的和存储在O(n ^ 2)空间中并在O(n ^ 2 logn)时间内对其进行排序.假设我们被允许具有相同的O(n ^ 2 logn)运行时间,我们如何将总和存储在O(n)的线性空间中？

我想我们并不打算存储所有的金额,因为它们n ^ 2个元素不适合n个空格,而且我们只是按排序顺序打印出所有内容,所以这是否意味着我们必须动态存储项目？有小费吗？

(这是作业问题)

我遇到了一个问题,我需要计算非常大的因子的值.我用两种不同的方式在C++中解决了这个问题,但只想知道我的复杂性分析是否准确.

在任何一种方法中,我将非常大的数字表示为v[0]表示最低有效数字的向量,而最后一个索引处的值表示最高有效数字.版本1的代码可以在这个要点中找到.

鉴于上面的代码,它似乎multiplyVectorByInteger()是O(log(n*k))其中n在给定的整数,并且k是由向量表示的数目.我的逻辑是,我们将做一些与结果数的长度成比例的步骤n*k,以产生一个向量表示n*k.长度n*k是O(log(n*k))一些步骤将在for循环中执行,其他步骤将在while循环中执行.

在这个程序中找到大的阶乘,每当我们调用时multiplyVectorByInteger()我们都会传入一个整数n和向量表示(n-1)!.这意味着如果我们想要查找6!,我们传入整数6和向量表示5!.该函数将返回矢量表示6!.使用以前的信息我相信我可以说复杂性是O(log(i!))我传递整数的地方.为了找到大的阶乘,我们必须调用此方法O(n)次,其中n是我们正在努力寻找阶乘.我们积累的逻辑将如下所示:

1!       = 1!
1!*2     = 2!
2!*3     = 3!
3!*4     = 4!
...
(n-1)!*n = n!

因为在我们计算的每个级别i!,我们因此O(log(i!))在每个级别执行步骤.总结如下:

我从第二次总结跳到Big-Oh表示法的逻辑如下......打破这个我们得到以下结果:

1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

很明显我们得到的O(n^2)条款log(1) + …

如果f(n)=O(g(n)),那么不应该f(n)?log2(f(n)^c)=O(g(n)?log2(g(n)))依赖于C的值？

这里C是正常数.根据我的说法,如果C很大,那么声明将变为假,如果c很小,那么它就是真的.因此结果取决于c.

我正在上课算法,这是我被问到的问题之一.据我说,这应该依赖于常数c,但答案是错误的.

我正在做一个性能关键程序(很少学术),我正在寻求尽可能优化(不像它证明"这是"瓶颈).

我有一个自定义字典结构(.NET的包装Dictionary<,>),我会不断删除一个阶段的项目(按Key值).我需要Value删除的项目.现在我必须这样做:

T t;
if !TryGet(key, out t)
   return false;

Remove(key);

这是两次查找.我会喜欢这个:

public bool Remove(S key, out T value)
{
    // implementation
}

我知道框架中没有任何内容,但是某处有实现吗？如果是这样的话,我会用那个更改我的支持词典.

编辑:嗯,我知道这两个TryGetValue和Remove是O(1).只知道是否有任何集合结构只能在一次查找中产生相同的效果.正如我所说,我正在努力尽可能地优化.只是知道.

该算法std::includes采用两个有序范围并检查set2是否在set1中(即set2的每个元素是否包含在set1中)？

我想知道为什么eel.is/c++draft说这个算法的复杂性至多是2·(N1+N2-1)比较的？

:同样在陈述
1. cppreference
2. CPLUSPLUS

在我看来,它应该只是最多的2·N1比较,最糟糕的情况是max(set2) >= max(set1).

我正在尝试与朋友做作业,一个问题询问线性探测方法的搜索,添加和删除的平均运行时间.我认为它是O(n)因为它必须检查特定数量的节点,直到它找到一个要添加的开放节点.当搜索它从原始索引开始并向上移动直到找到所需的数字.但我的朋友说这是O(1).哪一个是对的？

我正在修改 Big O 和其他相关边界的正式定义，有些事情让我感到困惑。在我正在阅读的书中 (Skiena) Big O 被定义为：

f(n) = O(g(n)) 当存在一个常数 c 使得 f(n) 对于某个 n > n0 的值总是 <= c*g(n)

这对我来说通常是有意义的。我们只关心足够大的 n 值，以至于增长率实际上很重要。但是为什么将 g(n) 乘以 c？似乎我可以为 c 选择一个非常大的值，并通过消除较小的 g(n) 值的大小来使整个事情变得随意。

辅助问题：选择将算法分类为复杂性类时，是拇指的一般规则，只需根据大O的定义选择仍然保存的最低增长类？根据定义，将恒定时间算法分类为 O(n!) 似乎是有效的，因为 f(n) 将 <= c*g(n)。当然，这没有任何价值。

谢谢！

我不熟悉主定理,递归树和替换方法之外的递归求解技术.我猜测解决大O绑定的以下重现不会使用以下方法之一:

T(n) = T(n-1) + 2T(n-2) + 1