f(n)=5logn,g(n)=logn,用O,W,q表示函数f与g之间的关系

- O表示上界关系，即f(n) = O(g(n))表示存在正整数C和n0，使得对于所有n>=n0，都有f(n)<=C*g(n)。因此，我们可以写出5logn = O(logn)，即5logn是logn的上界。
- W表示下界关系，即f(n) = W(g(n))表示存在正整数C和n0，使得对于所有n>=n0，都有f(n)>=C*g(n)。因此，我们可以写出5logn = W(logn)，即5logn是logn的下界。
- Θ表示渐进紧确界关系，即f(n) = Θ(g(n))表示存在正整数C1、C2和n0，使得对于所有n>=n0，都有C1*g(n)<=f(n)<=C2*g(n)。因此，我们不能写出5logn = Θ(logn)，因为5logn既不是logn的上界也不是下界。

相关问题

对于下列各组函数f(n)和 g(n)，确定f(n)=O(g(n))或f(n)=2(g(n))或f(n)=0(g(n))，并简述理由。(1)f(n)=lognn^2;g(n)=logn+5

根据大O符号的定义，若存在正常数c和$n_0$，使得当$n\ge n_0$时，有$f(n)\le c\cdot g(n)$，则$f(n)=O(g(n))$。现在考虑题目中给出的$f(n)$和$g(n)$，我们有：

$f(n)=\log n\cdot n^2$

$g(n)=\log n+5$

我们需要证明$f(n)=O(g(n))$。

当$n$充分大时，我们有：

$f(n)=\log n\cdot n^2$

$=2\log n\cdot\frac{1}{2}n^2$

$=2\log n\cdot n\cdot\frac{1}{2}n$

$=2n\log n\cdot\frac{1}{2}n$

$=n\log n\cdot n$

$=n^2\log n$

现在我们需要找到正常数$c$和$n_0$，使得$n\ge n_0$时，$f(n)\le c\cdot g(n)$。

注意到当$n\ge 2$时，有：

$\log n+5\le 2\log n$

因此，我们可以取$c=2$，$n_0=2$，则当$n\ge 2$时，有：

$f(n)=n^2\log n\le 2n^2\log n\le 2\cdot(\log n+5)\cdot n^2=c\cdot g(n)$

因此，我们得到$f(n)=O(g(n))$。

n(logn) 2 是o(n 2 )的

### 回答1：
b'n(logn) 与 o(n^2) 之间的关系是 b'n(logn) 是 o(n^2) 的子集，也就是说，所有 b'n(logn) 的函数都是 o(n^2) 的函数，但是不是所有 o(n^2) 的函数都是 b'n(logn) 的函数。

### 回答2：
要证明 n(logn) 2 是 o(n 2 ) 的，我们需要证明 lim(n→∞) n(logn) 2 / n 2 = 0。

我们可以对 n(logn) 2 和 n 2 各自取对数，得到 2(logn)^2 和 2logn，因为 logn 是单调递增的，所以对于 n > e（e 是自然对数的底数），有 (logn)^2 > logn，即 2(logn)^2 > 2logn。

因此，我们可以将上面的等式改写为 lim(n→∞) 2(logn)^2 / nlogn，进一步化简得到 lim(n→∞) 2logn / n = 0，这是显然成立的，因为对于任何正数 k，总有 lim(n→∞) logn / n^k = 0。

因此，我们已经证明了 n(logn) 2 是 o(n 2 ) 的。这个结论也可以直观地理解：logn 是比线性增长慢的函数，因此(logn)^2 是比 n 的增长更慢的函数，乘上一个 logn 就更小了，因此 n(logn) 2 是比 n 2 更小的函数。

### 回答3：
首先，我们需要了解Big-O符号与logarithm的关系。Big-O符号通常用于衡量算法的时间复杂度，而logarithm则是一个函数。在算法设计中经常出现O(log n)的时间复杂度，这表示运行时间与输入规模n的对数成正比。例如，二分查找算法的时间复杂度就是O(log n)。

现在，我们来看O(n log n)与O(n^2)的关系。通常情况下，O(n log n)的时间复杂度更优于O(n^2)。这是因为对于一个非常大的n，logarithm函数增长得比polynomial函数慢。因此，如果我们要比较O(n log n)和O(n^2)，需要使用Big-O符号，而不是通过比较函数的增长速度来判断。

O(n log n)表示一个算法的运行时间与n与n的对数之积成正比。例如，归并排序和快速排序算法的时间复杂度都是O(n log n)。而O(n^2)则表示一个算法的运行时间与n的平方成正比。例如，冒泡排序和插入排序算法的时间复杂度都是O(n^2)。

由于logarithm函数的增长速度比polynomial函数慢，因此O(n log n)的时间复杂度要优于O(n^2)的时间复杂度。因此，我们可以得出结论：O(n log n)是O(n^2)的一个子集，即O(n log n)的时间复杂度包含在O(n^2)的时间复杂度之内。也就是说，对于任何一个O(n^2)的算法，它的运行时间也一定不会超过O(n log n)。所以，我们可以得出结论：n(logn) 2 是o(n 2 )的。