标签: asymptotic-complexity

我的一位同事问我以下问题.

Which of the following expressions is not sublinear?
O(log log n)
O(n)
O(logn)
O(root(n))

我已经浏览了https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time但不能,但我不确定我是否完全了解它.有人能指出我正确的方向.

在CLRS(Cormen,Leiserson,Rivest和Stein的算法导论)中,用于函数

˚F(Ñ)= 一个² + BN + Ç

他们说

假设我们取常数c ₁ = a/4,c ₂ = 7 a/4,并且n ₀ = 2·max(| b |/a,√(| c |/a)).
然后0≤ c ^ ₁ ñ ² ≤ 的² + BN + c ^ ≤ c ^ ₂ Ñ ²对于所有Ñ ≥ Ñ ₀.
因此f(n)是Θ(n ²).

但他们没有具体说明这些常数的价值是如何产生的？
我试图证明它但不能.
请告诉我这些常数是怎么来的？

我想用递推方程找出程序的时间复杂度.那是 ..

int f(int x)
{
if(x<1) return 1;
 else  return f(x-1)+g(x); 
}
int g(int x)
{
if(x<2) return 1;
 else return f(x-1)+g(x/2);
}

我写了它的递推方程并尝试解决它,但它继续变得复杂

T(n) =T(n-1)+g(n)+c
         =T(n-2)+g(n-1)+g(n)+c+c
         =T(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c
         =T(n-4)+g(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c+c
         ……………………….
        ……………………..
        Kth time …..
        =kc+g(n)+g(n-1)+g(n-3)+g(n-4).. .. . … +T(n-k)

Let at kth time input become 1
Then n-k=1
         K=n-1
Now i end up with this..
T(n)= (n-1)c+g(n)+g(n-1)+g(n-2)+g(n-3)+….. .. g(1)

我无法进一步解决它.如果我们计算这个程序中函数调用的数量,可以很容易地看出时间复杂度是指数级的,但我想用重复证明它.怎么做到呢 ？

在Anwer 1中的解释,看起来正确,我做过类似的工作.

这段代码中最困难的任务是写出它的递归方程.我已经绘制了另一个图,我确定了一些模式,我认为我们可以从这个图中得到一些帮助,可能是可能的递归方程.

And I came up with this equation , not sure if it is right ??? …

我正在计算像这样的kruskal算法的时间复杂度(请参阅图像附加中的算法)

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

CLRS算法:

这是正确的还是我做错了请告诉我.

我很难用O表示法定义以下算法的运行时间.我的第一个猜测是O(n),但是迭代和我应用的数字之间的差距并不稳定.我怎么错误地定义了这个？

public int function (int n ) 
{
  if ( n == 0) {
    return 0;
  }

  int i = 1;
  int j = n ;
  while ( i < j ) 
  {
    i = i + 1;
    j = j - 1;
  }
  return function ( i - 1) + 1;
}

我想知道是否有可能表达依赖于使用Big O表示法收敛的算法的时间复杂度.

在我看过的大多数算法分析中,我们根据输入大小来评估函数的增长率.

在具有一些收敛标准的算法的情况下(我们重复操作直到某个定义的误差度量低于阈值,或者误差度量变化的速率低于某个阈值),我们如何测量时间复杂度？收敛和退出该循环所需的迭代次数似乎很难推理,因为算法收敛的方式往往取决于输入的内容而不仅仅是它的大小.

我们如何表示依赖于Big O表示法收敛的算法的时间复杂度？

在遇到复发时,我遇到了忽略地板和天花板的地方.

CLRS (第4章,第83页)的例子,其中忽略了最低限度:

这里(第2 页,练习4.1-1)是一个忽略上限的例子:( 编辑:我从公众舆论中得知这有点可疑.)

事实上,在CLRS(第88页)中,它提到:

"解决复发问题时,地板和天花板通常无关紧要"

我的问题:

1. 这里"通常"是指所有情况？如果是的话,我可以一直忘记它们.
2. 如果没有,那么在解决复发问题时,地板和天花板何时真正算在内？

注意:这不是作业问题.当我刷新DS和算法时,我想到了这一点.

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

从SortedSet<T>.GetEnumerator文档:

该方法是O(1)操作

从SortedDictionary<K, V>.GetEnumerator文档:

此方法是O(log n)操作,其中n是count.

这两个陈述都可以是真的,考虑到SortedDictionary<K, V>内部实现为SortedSet<KeyValuePair<K, V>？我检查了类的GetEnumerator代码SortedDictionary- 它直接使用了SortedSet枚举器.我注意到了SortedSet枚举器的实现,在我看来它确实有O(log n)特性(这里是代码):

public SortedSet<T>.Enumerator GetEnumerator()
{
  return new SortedSet<T>.Enumerator(this);
}

//which calls this constructor:
internal Enumerator(SortedSet<T> set)
{
  this.tree = set;
  this.tree.VersionCheck();
  this.version = this.tree.version;
  this.stack = new Stack<SortedSet<T>.Node>(2 * SortedSet<T>.log2(set.Count + 1));
  this.current = (SortedSet<T>.Node) null;
  this.reverse = false;
  this.siInfo = (SerializationInfo) null;
  this.Intialize();
}

private void Intialize()
{
  this.current = (SortedSet<T>.Node) null;
  SortedSet<T>.Node …

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

数学上,对于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)？