n b = o(a n ) (o is little oh) 是什么意思？我刚开始自学我的算法，每次看到这样的表达我都很难解释。在这里，我的理解是对于函数 n b，增长率是n。但这对我来说没有意义，无论是对还是错。
问问题
1784 次
3 回答
1
陈述 n b的超高级含义是 o(a n ) 只是像 a n 这样的指数函数比像 n b这样的多项式函数增长得快得多。
在查看大 O 和小 o 符号时要理解的重要一点是它们都是上限。我猜这就是你感到困惑的原因。n b是 o(an n ) 因为 a n的增长率要大得多。您可能会在 n b上找到一个更严格的小 o 上限（边界和函数之间的差距更小），但 a n仍然有效。大 O 和小 o 之间的区别可能也值得一看。
请记住，函数 f 是函数 g 的大 O，如果对于某个常数 k > 0，您最终可以找到 n 的最小值，使得 f(n) ≤ k * g(n)。
如果对于任何常数 k > 0，您最终可以找到 n 的最小值，使得 f(n) ≤ k * g(n)，则函数 f 是函数 g 的小 o 。
请注意，小 o 要求更难满足，这意味着如果函数 f 是函数 g 的小 o，那么它也是g 的大 O，这意味着函数 g 的增长速度比仅是 g 的大 O 快.
在您的示例中，如果 b 为 3，a 为 2，并且我们将 k 设置为 1，我们可以计算出 n 的最小值，使得 n b ≤ k * a n。在这种情况下，它介于 9 和 10 之间，因为
9³ = 729and1 * 2⁹ = 512表示在 9 时 a n尚未大于 n b
但是
10³ = 1000and1 * 2¹⁰ = 1024表示n现在大于 n b。您可以看到绘制这些函数的图形，对于 n > 10 的任何值，n都将大于 n b。此时，我们仅证明 n b是n的大O ，因为 Big O 仅要求对于某些k 值> 0（我们选择了 1）n ≥ n b对于某个最小值 n（在这种情况下，它在 9 到 10 之间）
为了证明 n b是 a n的小 o ，我们必须证明对于任何大于 0 的 k，您仍然可以找到 n 的最小值，使得 a n > n b。例如，如果您选择 k = .5，我们之前发现的最小值 10 不起作用，因为10³ = 1000和.5 * 2¹⁰ = 512。但是我们可以继续将 n 的最小值越来越远，k 越小，n 的最小值 b 就越大。说 n b is little o of a n意味着无论你使 k 多么小，我们总是能够为 n 找到一个足够大的值，使得 n b ≤ k * a n
于 2014-01-06T06:37:48.837 回答
1
f(n)=o(g(n))意味着f(n)/g(n)->0当n->infinite.
对于您的问题，它应该成立a>1。(n^b)/(a^n)->0当 n-> 无限时，因为(n^b)/(sqrt(a)^n*sqrt(a)^n))=((n^b)/sqrt(a)^n) * (1/sqrt(a)^n). Letf(n)=((n^b)/sqrt(a)^n)是一个函数先增后减，所以可以得到 的最大值max(f(n))=M，然后(n^b)/(a^n) < M/(sqrt(a)^n)，因为a>1, sqrt(a)>1，所以(sqrt(a)^n)->infinite当n->infinite。那就是M/(sqrt(a)^n)->0当n->infinite，最后，我们得到(n^b)/(a^n)->0当 n->infinite 的时候。这是n^b=o(a^n)根据定义。
于 2014-01-06T06:58:11.490 回答
1
（为简单起见，我假设所有函数总是返回正值。例如，测量算法运行时间的函数就是这种情况，因为没有算法在“负”时间运行。）
首先，回顾一下大 O 表示法，以澄清一个常见的误解：
说那f是O(g)意味着f渐近增长最多与 一样快g。更正式地说，将f和都g视为变量 的函数，n也就是说f(n)，O(g(n))有一个常数K，所以最终，f(n) < K * g(n)。这里的“最终”一词意味着存在某个固定值N（它是 、 和 的函数K）f，g因此如果n > N则f(n) < K * g(n)。
例如，函数f(n) = n + 2是O(n^2)。要了解原因，让K = 1. 那么，如果n > 10，我们有n + 2 < n^2，那么我们的条件就满足了。需要注意的几点：
- 因为
n = 1, 我们有f(n) = 3并且g(n) = 1, 所以f(n) < K * g(n)实际上失败了。没关系！请记住，不等式只需要最终成立，对于一些小的有限列表，不等式是否失败也没关系n。 - 我们用过
K = 1，但我们不需要。例如，K = 2也可以工作。重要的是，它的某些价值K最终会为我们提供我们想要的不平等。 - 我们看到的
n + 2是O(n^2)。这可能看起来令人困惑，您可能会说，“等等，n + 2实际上不是O(n)吗？” 答案是肯定的。n + 2是O(n),O(n^2),O(n^3),O(n/3)等
Little-o 符号略有不同。Big-O 表示法直观地说，如果f是O(g)，则f渐近增长最多与 一样快g。Little-o 表示法表示如果f是o(g)，则严格地f渐近地比慢。g
形式上，f如果对于 的任何（o(g)假设是肯定的）选择K，最终不等式f(n) < K * o(g)成立。因此，例如：
- 功能
f(n) = n不是。_o(n)这是因为，对于K = 1，不存在nso that的值f(n) < K * g(n)。直观地，f并且以相同的速率g渐近增长，因此严格来说不会比实际增长慢。fg - 功能
f(n) = n是o(n^2)。为什么是这样？选择你最喜欢的正值K。（要查看实际点，请尝试K缩小，例如 0.001。）想象一下绘制函数f(n)和K * g(n)。一种是通过正斜率原点的直线，另一种是通过原点的上凹抛物线。最终，抛物线将高于这条线，并将保持这种状态。（如果你记得你的预计算/微积分......）
现在我们来解决您的实际问题：让f(n) = n^b和g(n) = a^n。你问f为什么o(g)。
据推测，原始陈述的作者将a和b视为常数，正实数，而且a > 1（如果a <= 1陈述为假）。
用英语写的声明是：
对于任何正实数
b和任何实数a > 1，函数的n^b渐近增长都严格慢于a^n。
如果您要处理算法复杂性，了解这一点很重要。更简单地说，可以说“多项式的增长速度比指数函数慢得多”。这不是很明显，这是真的，而且写得太多了，所以这里有一个参考：
可能您必须对数学有一定的了解才能阅读有关这一事实的任何证据。
祝你好运！
于 2014-01-06T07:17:37.900 回答