请证明 T(n)=n^4+2n^3+3n^2+10n 的上限即是 O(n^4) 也是 O(n^5).
时间: 2023-11-13 21:38:44 浏览: 54
首先我们证明 T(n) = n^4 + 2n^3 + 3n^2 + 10n 是 O(n^4)。根据大 O 表示法,我们需要找到一个常数 C 和一个正整数 N,使得对于所有的 n>N,都有 T(n) <= C * n^4。
我们可以将 T(n) 的每一项都变成 n^4 的形式,即:
T(n) = n^4 + 2n^3 + 3n^2 + 10n
<= n^4 + 2n^4 + 3n^4 + 10n^4 (当 n>1 时,n^4 > 10n^3 > 3n^2 > 2n)
= 16n^4
因此,我们可以取 C=16,N=1,即可证明 T(n) 是 O(n^4)。
接着,我们证明 T(n) 是 O(n^5)。同样,我们需要找到一个常数 C 和一个正整数 N,使得对于所有的 n>N,都有 T(n) <= C * n^5。
根据 T(n) 的表达式,我们可以得到:
T(n) = n^4 + 2n^3 + 3n^2 + 10n
<= n^5 + 2n^5 + 3n^5 + 10n^5 (当 n>1 时,n^5 > 10n^4 > 3n^3 > 2n^2)
= 16n^5
因此,我们可以取 C=16,N=1,即可证明 T(n) 是 O(n^5)。
综上所述,T(n) 的上限既是 O(n^4),也是 O(n^5)。
相关问题
求表达式3n^2+10n的上界 结果为n0= C= g(n)
我们可以使用大O符号来表示上界。要求表达式3n^2+10n的上界,我们可以找到一个函数g(n),满足3n^2+10n小于等于C*g(n)。其中C为一个常数。
我们可以将3n^2+10n拆开,得到3n^2和10n。对于3n^2,我们可以找到一个常数k1,使得n大于等于n0时,3n^2小于等于k1*n^2。对于10n,我们可以找到一个常数k2,使得n大于等于n0时,10n小于等于k2*n。
因此,当n大于等于n0时,3n^2+10n小于等于k1*n^2+k2*n。我们可以取C等于k1+ k2,g(n)等于n^2,因此,3n^2+10n的上界为O(n^2)。
证明13𝑛3+ 7n log n + 3 is O(𝑛3)
要证明13𝑛^3+ 7n log n + 3是O(𝑛^3),我们需要找到一个正常数C和一个正整数𝑛0,使得当𝑛≥𝑛0时,13𝑛^3+ 7n log n + 3 ≤ C𝑛^3。
我们可以将这个不等式分成两部分,分别考虑:
1. 当n趋近于正无穷时,13𝑛^3的增长速度远大于7n log n和3的增长速度,因此我们可以忽略后两项,得到13𝑛^3 ≤ 13𝑛^3。
2. 要证明13𝑛^3+ 7n log n + 3是O(𝑛^3),我们需要找到一个正常数C和一个正整数𝑛0,使得当𝑛≥𝑛0时,13𝑛^3+ 7n log n + 3 ≤ C𝑛^3。我们可以选择C=14(即13+7log2+3/𝑛^3),并且选择𝑛0=1,因为当𝑛≥1时,7n log n + 3 ≤ 7n^2 + 3n^2 = 10n^2,因此13𝑛^3+ 7n log n + 3 ≤ 13𝑛^3+ 10n^2 ≤ 14𝑛^3。
因此,我们可以得出结论:13𝑛^3+ 7n log n + 3是O(𝑛^3)。