巴赫曼-朗道符号家族

Question

巴赫曼-朗道符号家族

3

请帮我理解图片中提到的符号？我试图理解“Bachmann-Landau符号族”下面的“Big O符号”，在“形式定义”列中，有很多带有方程式的符号，我以前没有遇到过这些符号。有人熟悉吗？https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations

- user3764118

这些定义中到底什么让你感到困惑？你已经了解了哪些关于Big-O的知识？如果有不同的定义，你知道是哪个吗？目前你的问题比较宽泛，一个充分的答案需要全面解释Big-O这个大主题，以涵盖你可能意味着的所有内容。请只提出精确、非广泛性的问题（参见[ask]，[help]）。 - Zabuzard

@Zabuza，感谢您的时间，我对这些符号（A（反向）和E（反向））的理解有问题！ - user3764118

1

@user3764118，∀和∃是大多数数学中使用的典型数学符号。∀被称为全称量词，通常读作“对于所有”或“对于每个”，而∃则是存在量词，通常读作“存在（至少一个）...使得”。 - SergGr

@SergGr 是的，谢谢你，那就是我要找的！ - user3764118

1

@user3764118，例如，∀ k > 0 ∃ n0 ∀ n > n0 |f(n)| < k*g(n) 这一行应该被理解为“对于每个正的 k，都存在一个值 n0，使得对于每个 n 满足 n > n0，都有 |f(n)| < k*g(n)”。或者更通俗地说，对于每个正的倍数 k，你可以走得足够远（n0），在那之后的点（n > n0）上，|f(n)| 的值小于 k*g(n)。甚至更不正式地说，在无穷大时，f(n) “基本上比” g(n) 小。 - SergGr

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- libik · Accepted Answer

这些定义背后的逻辑其实非常简单，它基本上是说无论什么常数乘以结果，从某个足够大的点开始，函数之一将开始变得更大/更小，并保持这种状态。

为了看到真正的差异，我将解释一下“小o”（它表示某个函数的复杂度比其他函数小），它表示对于所有大于零的k，你可以找到一个名为n_0的值，使得所有大于n_0的n都遵循这个模式：f(n) <= k*g(n)。

因此，你有两个函数，然后将n作为参数放入其中。然后无论你放什么作为k，你总是能找到一个n的值，使得f(n) <= k*g(n)，而且所有大于你找到的那个值的值也符合这个等式。

例如，请考虑：

f(n) = n * 100
g(n) = n^2

所以，如果您尝试在那里放置n=5，它不会告诉您哪个复杂度更大，因为5*100=500和5^2=25。如果您放置的数字足够大，例如n=100，则f(n)=100*100=10000且g(n)=100^2=100*100=10000。因此，我们得到相同的值。如果您尝试放置比这更大的任何内容，g(n)将变得越来越大。

它还必须遵循方程式f(n) <= k*g(n)。例如，如果我放置k=0.1，那么

100*n <= 0.1*n^2 *10
1000n <= n^2 /n
1000 < n

使用这些函数，你可以看到对于 k=0.1，你需要 n_0 = 1000 来满足方程，但这已经足够了。所有大于 n > 1000 的值都会更大，因此函数 g(n) 总是更复杂。（好吧，真正的证明并不那么简单，但你可以看到这个模式）。关键是，无论 k 是什么，即使它等于 k=0.000000001，总会有一个 n_0 的破解点，从那时起，所有的 g(n) 都会比 f(n) 更大。

我们还可以尝试一些负数方程来看看 O(n) 和 O(n^2) 之间的区别。

让我们来看看：

f(n) = n
g(n) = 10*n

因此，在标准代数中，g(n) > f(n)，对吧？但在复杂性理论中，我们需要知道它是否增长更快，如果是这样，是否比简单地乘以常数增长更快。

因此，如果我们考虑k=0.01，那么可以看到无论n有多大，都找不到满足f(n) <= k*g(n)的n_0，因此f(n) != o(g(n)) 从复杂度理论的角度来看，可以将符号表示为更小/更大，因此

f(n) = o(g(n)) -> f(n) < g(n)
f(n) = O(g(n)) -> f(n) <= g(n)
f(n) = Big-Theta(g(n)) -> f(n) === g(n)
//... etc, remember these euqations are not algebraic, just for complexity