标签: big-theta

我正在学习使用麻省理工学院课件和CLRS书籍算法入门.

我目前正在尝试解决重复问题(来自第107页)

T(n)= 2T(n/2)+ n ⁴

如果我制作一个重复树,我得到:

0级:n ⁴

1级2(n/2)⁴

2级4(n/4)⁴

3级8(n/8)⁴

树有lg(n)级.因此,我认为应该再次发生

T(n)=Θ(n ⁴ lg n)

但是,如果我使用主定理,我就明白了

T(n)=Θ(n ⁴)

显然这两者都不对.哪一个是正确的？我的推理在哪里出错了？

我有一个关于几何级数的问题。为什么是

1 + c + c ² + ... + c ⁿ = ?(c ⁿ )

当 c > 1 时？我明白为什么它是 ?(n) if c = 1 并且它是 ?(1) if c < 1，但我就是不明白为什么它是 ?(c ⁿ ) if c>1。

谢谢！

我无法理解如何将其变成公式.

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j += i) {

我意识到会发生什么,对于每个i ++,你有1级乘法而不是j.

i = 1,你得到j = 1,2,3,...,100

i = 2,你得到j = 1,3,5,......,100

我不确定如何用Big-theta来思考这个问题.

总的j是N,N/2,N/3,N/4 ...,N/N(我的结论)

怎么最好尝试将其视为N的函数？

我有公式a(n)= n*a(n-1)+1; a(0)= 0

如果没有主定理,我如何从中得到Omega,Theta或O表示法,或者有没有人有一个很好的网站来理解解释

我在Interview Bit上解决了时间复杂度问题,如下图所示.

给出的答案是?(theta)(logn),我无法掌握登录术语如何到达此计划的时间复杂性.

有人可以解释一下logn的答案是什么？

开始学习算法.我理解如何从'常规复发'中找到theta-notation T(n) = Tf(n) + g(n).但是我对这种复发感到迷茫:问题1-2e:

T(n)= T(√n)+Θ(lg lg n)

如何选择找到theta的方法？什么,呃,这种复发是什么？我只是不太明白符号 - 内部复发的事情.

我明白为什么在链式哈希表中搜索不成功的时间复杂度平均为 ?(1+​​(n/m))，因为在不成功搜索中检查的元素的预期数量是 (n/m)，并且总数所需时间（包括计算hashFunction(key)的时间）为?(1+(n/m))。但是为什么搜索成功的结果是一样的呢？

sum = 0;
for(int i = 0; i < N; i++)
    for(int j = i; j >= 0; j--)
       sum++;

据我所知,第一行是1次操作,第2行是(i+1)操作,第3行是(i-1)操作,第4行是n操作.这是否意味着运行时间1 + (i+1)(i-1) + n？只是这些让我困惑的最后一步.

我正在开发一些占用O(log ^ 3 n)的算法.(注意:把O视为大Theta,虽然Big O也会很好)

我不确定,而O(log ^ 3 n),甚至O(log ^ 2 n),被认为是O/n(n log n)更多/更少/等于复数.

如果我要严格遵守规则,我会说O(n log n)是更复杂的规则,但我仍然没有任何线索,为什么或如何.

我已经做了一些研究但是我找不到这个问题的答案.

非常感谢你.

假设我们开始使用如下文本文件:

a 00 
b 01
c 10
d 11

00000001011011

该算法将是您使用前缀来构建霍夫曼树的典型算法,在遍历树时读取编码位,直到到达叶子,然后在该叶子处返回字符.

有人可以解释我如何确定运行时间和空间复杂度？