f(n)在O( g(n) )中，它能有与g(N)相同的增长吗？
在给出答案之前，我想先解释一下问题中的一些概念。
- f(n)和g(n)：这里的f(n)和g(n)是函数，表示随着输入规模n的增长，函数的执行时间或者资源消耗等指标的增长情况。
- O( g(n) )：这是一种表示算法复杂度的记号，表示函数f(n)的增长情况不会超过g(n)的增长情况。具体来说，如果f(n)在O( g(n) )中，意味着存在一个常数C和一个正整数N，使得对于所有n>N，f(n) <= C * g(n)。
现在来回答问题：f(n)在O( g(n) )中，它能有与g(N)相同的增长吗？
根据O记号的定义，f(n)在O( g(n) )中意味着f(n)的增长情况不会超过g(n)的增长情况。因此，f(n)不可能有与g(n)相同的增长。
举个例子来说明，假设f(n) = n^2，g(n) = n。显然，f(n)的增长情况是二次的，而g(n)的增长情况是线性的。因此，f(n)在O( g(n) )中，但它的增长情况与g(n)不同。
总结起来，f(n)在O( g(n) )中，它不可能有与g(n)相同的增长。
相关·内容
我知道f(n)的增长速度比g(n)慢，但既然有等号，f(n)的增长速度能和g(n)一样吗？
浏览 18提问于2021-09-23得票数 0
给定PHP中的两个函数，例如 return $n; return pow($n, (2/3));如何检查函数f(n)是否在Ω(g(n))、Θ(g(n))或O(g(n))<
浏览 3提问于2014-03-14得票数 0
回答已采纳
O代表大O。O(g)：{ f| f是非负函数使得f(n) <= cg(n)对于所有n >= m}
Show That :- O( f(n) +g(n) ) = O( max{ f(n) , <
浏览 0提问于2010-11-20得票数 2
给定f(n) = n^(1+sin(n*pi/2))/2和g(n) = n^0.5，如何证明f(n) = O(g(n)) / f(n) = Omega(g(n)) / f(n) = Theta(g(n
浏览 22提问于2019-03-07得票数 1
2回答
确定渐近复杂度
、、、、
如果给我两个函数，并要求我计算这两个函数的渐近复杂度，这意味着什么？是O()还是Big Theta？例如f1(n)=a^n和f2(n)=n^3+n^2
我应该说f1是O(a^n)，f2是O(n^3)，还是应该使用big-theta？
浏览 2提问于2013-09-16得票数 2
1回答
我正在寻找一个简单的例子函数f(n)，它是其他函数g(n)的大O，但不是g(n)的小o。换句话说，有些f(n)使得f(n)是O(g(n))，而不是o(g(n))。我能想到的最简单的情形是
浏览 3提问于2020-02-06得票数 4
回答已采纳
1回答
我的教授最近提到了“大O”的正式定义：老实说，即使在他向几个不同的学生解释了它之后，我们似乎仍然不理解它的核心。理解中的问题主要发生在下面的例子中：到目前为止，我的理由如下：
当你把一个函数的最高项乘以一个常数时，你会得到一个新的函数，它最终超过了给定的n上的初始函数。他称这个n
浏览 2提问于2021-11-30得票数 5
2回答
算法的增长函数？
、、、
我有两个问题：-
，如果f(n)是求增长率的函数，那么，对于所有三种符号，g(n)是否是相同的，就像f(n)=O(g(n))一样，对于omega和theta， theta表示法是"omega和Oh“，如果在某些情况下，如果o和omega函数是不同的，那么我们怎么能在那里找到θ函数呢？
浏览 3提问于2012-05-07得票数 3
1回答
关于函数中大O的定义但是，用大O表示法描述函数，通常只提供函数增长率的上界。因此，在这里，34是集合{ 5, 10, 34 }的上限因此，如果在这个图中f(n
浏览 2提问于2015-05-12得票数 0
回答已采纳
2回答
算法中的大O
、、
我读了一篇文章，发现了以下内容：
非正式地说，O( g(n) )可以定义为一组数学函数，其中包含的所有函数都不会比g(N)“增长得更快”。因此，下面的所有函数都在O(n平方)：f(n) = n²+3n + 2, f(n) = n log(n), f(n) =
浏览 7提问于2021-11-06得票数 0
大θ，它既是大o又是大ω。据我所知，大o是上限，这意味着对于任何大的输入，复杂度不应该超过大o，而对于大omega，复杂度则相反。大θ有多大，大o和大ω，这意味着如果我在图中看到，大o和大ω将是同一条线。或者换句话说，如果我们找到一个问题的解决方案，无论我们尝试的输入有多小或多大，复杂度都是一样的。这是它的意思吗？
浏览 0提问于2019-07-26得票数 1
我这里用的是大号。设f(n)和g(n)是两个时间复杂度相等于O(n)的函数。根据定义(当使用"=“来解释时间复杂性时)，这种推理可能是正确的：
IF f(n)=O(n) AND g(n)=O(n) THEN f(n)=g(
浏览 0提问于2017-06-23得票数 1
回答已采纳
我可以证明这一点，但我在概念上不明白为什么3^n在O(10^n)中。我说错了吗？
浏览 2提问于2016-04-06得票数 0
例如，像下面的问题一样，我可以通过做极限比较测试来解决这个问题吗？设f(n) =n·(4^n)，g(n) = 2^(3n)f(n)≤O(g(n))，f(n)≥Ω(g(N))，或者f(n) =Θ(g(n)
浏览 3提问于2020-05-03得票数 0
2回答
我最近进行了一次争论/辩论，我正试图对正确的解决办法作出明确的判断。for i from 0 to n! do:假设输入是n，那么它的复杂性显然是O(n!) (甚至是ϴ(n!)现在让我们假设这个程
浏览 0提问于2016-01-25得票数 4
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
