0

除了 Big O 之外,我无法理解时间复杂度。在这个例子中:

f(n) = n^10 g

g(n) = (2n)^10

是 f θ(g) 吗?我猜它是 θ(g) 因为你可以找到一个常数 c1 和 c2 将允许 c1*g(n) 成为 f(n) 的上限,而 c2*g(n) 将成为下限.

4

1 回答 1

1

参见,f(n)=n^10 和 g(n)=(2n)^10。

因此,f(n)>=((1/4)^10)*(2n)^10大于 g(n)。所以,f(n)>=c1*g(n)对于一些 c1=1/4;

类似地,对于任何大于或等于 1/2f(n)<=(c2)/*(2n)^10的 c2 值,它都小于 g(n) 。

所以,f(n)<=c2*g(n)

因此c1*g(n)<=f(n)<=c2*g(n); where c1<1/2 and c2>1/2

因此,f(n)=Theta(g(n))f(n)=θ(g(n))

于 2014-06-10T02:24:29.407 回答