用big theta分析算法

Question

我不得不说这三种算法的时间复杂度。是否有人可以看出他们是否正确？

我也不确定我是如何找到theta的？

我知道theta是big-O和Omega的平均值。但是我觉得在分析代码并用big-O表示法编写代码时基本相同。

Answer 1

第一个似乎是正确的，下面的解释，Θ表示法的定义如下

Θ(g(n)) = {f(n) : there exists c1,c2,n0 such that
                 0 <= c1*g(n) <= f(n) <= c2*g(n) given c1,c2,n0 > 0}

在第一个片段中，我们应该寻找f（n）

f(n)= n/3 + n/5 = 8/15*n

如果我们假设c1 = 0.5，c2 = 2，n0 = 15（因为可以被3和5整除），那么找到g（n）

when n=15, 0<=c1g(n)<=f(n)<=c2g(n)  =>  0<=c1g(n)<=1*8/15*15<=c2g(n)  =>  0<=0.5*g(n)<=8<=2*g(n)
when n=30 0<=0.5g(n)<=16<=2g(n)
when n=90 0<=0.5g(n)<=48<=2g(n) ...so on

when n=17 0<=0.5g(n)<=9<=2g(n)
when n=20 0<=0.5g(n)<=10<=2g(n)

因此g（n）= n似乎是合适的选择，因为我们可以证明c1，c2和n0的一个组合证明定义是正确的，g（n）= n是可接受的答案。