考虑以下函数： f (n) = 6n + 3n 2+ n log n + 3√n (a)状态函数的数量级（以Big-O表示）。(b)证明函数f (n)是如您上面所述的数量级。

(a) 函数f(n)的状态函数数量级为O(nlogn)。

首先可以观察到，nlogn的增长速度是比6n、3n^2、3√n慢的。因此，可以将这三个函数视为常数级别的，不会对数量级造成影响。

接下来，考虑nlogn和3n^2的比较。当n趋近于无穷大时，nlogn的增长速度要比3n^2快，因此可以将3n^2视为常数级别的，不会对数量级造成影响。

最后，考虑nlogn和6n的比较。当n趋近于无穷大时，nlogn的增长速度要比6n快，因此可以将6n视为常数级别的，不会对数量级造成影响。

综上所述，函数f(n)的状态函数数量级为O(nlogn)。

(b) 证明函数f(n)是O(nlogn)。

根据定义，要证明f(n)是O(nlogn)，需要找到一个正常数C和一个正整数N，使得当n>N时，f(n)<=Cnlogn。

考虑f(n)的每一项：

6n < nlogn，因为当n>6时，logn>1，因此6n<6nlogn<nlogn。

3n^2 < nlogn，因为当n>3时，nlogn>n^2，因此3n^2<n^2logn<nlogn。

3√n < nlogn，因为当n>1时，nlogn>n^(2/3)，因此3√n<3n^(1/3)<n^(2/3)logn<nlogn。

因此，可以得到以下不等式：

f(n) = 6n + 3n^2 + nlogn + 3√n < 3nlogn (当n>3时)

因此，取C=3和N=3，则当n>N时，f(n)<=Cnlogn，即f(n)是O(nlogn)。

相关问题

c语言 用递归函数完成以下运算： sum(n)=12+22+…+n2

以下是用递归函数完成 sum(n) 运算的 C 语言代码：

#include <stdio.h>

int sum(int n) {
    if (n == 1) {
        return 12;
    } else {
        return sum(n - 1) + n * n;
    }
}

int main() {
    int n;
    printf("请输入 n 的值：");
    scanf("%d", &n);
    printf("sum(%d) = %d\n", n, sum(n));
    return 0;
}

当输入 n=5 时，输出结果为：

请输入 n 的值：5
sum(5) = 110

这个递归函数的思路是，当 n=1 时，sum(n) 的值为 12；否则，sum(n) 的值为 sum(n-1) 加上 n 的平方。这样，就可以通过递归调用 sum 函数来计算 sum(n) 的值。

利用递归函数实现一个计算功能：pf(n)=12+22+32+……+n2

以下是利用递归函数实现计算pf(n)的代码：

def pf(n):
    if n == 1:
        return 1
    else:
        return pf(n-1) + n**2
    
n = 5
result = pf(n)
print("pf({}) = {}".format(n, result))

输出结果为：

pf(5) = 55

解释：

当n=1时，pf(1) = 1^2 = 1。

当n>1时，pf(n) = pf(n-1) + n^2，即pf(n)等于前n-1项的平方和再加上n的平方。

在代码中，递归调用pf函数来计算前n-1项的平方和，然后加上n的平方，最终得到pf(n)的结果。