基于渐近符号比较两个函数
Comparing two functions based on Asymptotic notations
f(n)= 1 + 2 + 3 + · · + n
g(n) = 3(n^2) + nlogn
确定 f = O(g) 或
f = Ω(g) 或 f = Θ(g)
。根据我的努力和理解,一个猜测可能是 f=O(g),因为 g(n) 的 n^2 幂比 n 增长得更快。
另一种方式:如果同时除以 n,f(n) 将有一个常量 1 和 g(n):nlogn 比常量 1 增长得更快。所以 , f=O(g) 。
这是正确答案吗?
Big-O 的缩放 属性 究竟是什么?
如何证明:对于任何常数 c > 0,cf(n) 是 O(f(n)).
到目前为止的理解:
cf(n) < (c + k)f(n) 对所有 n > 0 和 k > 0 成立。
我。常数因子被忽略。
二。只应利用 n 的权力和功能
正是这种对恒定因素的忽略激发了这种
符号。这证明 f 是 O(f).
这个解释是否足以证明 Big-O 的缩放 属性?
f(n)=O(g(n)) 如果存在一个正常数 c 例如。
|f(n)| <= c*|g(n)|对于所有 n>=n(初始)
并且由于 f(n)=(n(n-1))/2 ----> (n^2)
n^2<= n^2 + nlogn(忽略常量),对于所有 n>=1 那么是的,你的答案是正确的。
f(n)= 1 + 2 + 3 + · · + n
g(n) = 3(n^2) + nlogn
确定 f = O(g) 或 f = Ω(g) 或 f = Θ(g)
。根据我的努力和理解,一个猜测可能是 f=O(g),因为 g(n) 的 n^2 幂比 n 增长得更快。
另一种方式:如果同时除以 n,f(n) 将有一个常量 1 和 g(n):nlogn 比常量 1 增长得更快。所以 , f=O(g) 。 这是正确答案吗?
Big-O 的缩放 属性 究竟是什么? 如何证明:对于任何常数 c > 0,cf(n) 是 O(f(n)).
到目前为止的理解: cf(n) < (c + k)f(n) 对所有 n > 0 和 k > 0 成立。
我。常数因子被忽略。
二。只应利用 n 的权力和功能 正是这种对恒定因素的忽略激发了这种 符号。这证明 f 是 O(f).
这个解释是否足以证明 Big-O 的缩放 属性?
f(n)=O(g(n)) 如果存在一个正常数 c 例如。 |f(n)| <= c*|g(n)|对于所有 n>=n(初始)
并且由于 f(n)=(n(n-1))/2 ----> (n^2)
n^2<= n^2 + nlogn(忽略常量),对于所有 n>=1 那么是的,你的答案是正确的。