用大 theta 分析算法
Analysing algorithm with big theta
不得不说一下这三个算法的时间复杂度。
有人可以看看他们是否正确吗？
我也不确定如何找到 theta？
我知道 theta 是 big-O 和 Omega 的平均值。但是我感觉在分析代码和写大O的时候基本是一样的。
下面的解释第一个似乎是正确的，Θ符号的定义如下
Θ(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 是可接受的答案。
不得不说一下这三个算法的时间复杂度。 有人可以看看他们是否正确吗？
我也不确定如何找到 theta？
我知道 theta 是 big-O 和 Omega 的平均值。但是我感觉在分析代码和写大O的时候基本是一样的。
下面的解释第一个似乎是正确的，Θ符号的定义如下
Θ(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 是可接受的答案。