com*_*ist 1 algorithm complexity-theory big-o
设f(n)和g(n)复杂度起作用.为什么这句话适用？我怎么能证明这一点？
这个命题显然是错误的.考虑f(n)=n和g(n)=0.min(f(n),g(n))是零n>=0,但是f(n)-g(n) = n,不是O(0).
对于每一个n>=0,f(n)-g(n) <= f(n)所以f(n)-g(n)是O(f(n)).我认为这是一般可以做出的最强烈的陈述,没有下限,g(n)这是一个积极的功能n.
================================================== ========================
上面的第二段是不正确的,因为正如@Dukeling在评论中指出的那样,g(n)可能是如此之大以至于f(n)-g(n)是否定的,可能具有大于的绝对量值f(n).在这种情况下会发生什么取决于big-O的定义.
甲NIST网页定义它如下:"形式化定义:F(N)= O(G(N))意味着有正的常数C和K,使得0≤F(N)≤CG(n)的对所有的n ≥k.对于函数f,c和k的值必须是固定的,并且不得取决于n."
根据该定义,对于每个正数k具有至少一个n>=k为f(n)负数的函数不是大O任何东西.
甲维基百科页面定义它如下(折算为ASCII):f(x) = O(g(x))当且仅当存在正的实数M和的实数x_0,使得
|f(x)| <= M |g(x)| for all x>x_0
通过使用其绝对值,此定义允许对大型参数值为负的函数使用big-O表示法.有了这个定义,f(n)-g(n)就是O(max(f(n),g(n))).