巴赫曼-朗道符号族
Family of Bachmann–Landau notations
请帮我理解图中提到的符号？，我试着理解"Big O notation"在[=18下=] Table 有 "Formal Definition" 列，里面有很多带方程的符号，我以前没有遇到过这些符号。任何人都可以熟悉这个吗？ https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations
定义背后的逻辑其实很简单，它基本上是说无论什么常数乘以结果，从某个点 n 足够大，函数之一将开始成为bigger/smaller 并且一直如此。
为了看到真正的区别，我将解释 small-o（表示某些函数的复杂度低于其他函数），它表示对于所有大于零的 k，您可以找到一些值n 调用了 n_0，其中所有 n 大于 n_0 的都遵循以下模式：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))
在复杂性理论方面，您可以将符号视为 smaller/bigger，因此
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
请帮我理解图中提到的符号？，我试着理解"Big O notation"在[=18下=] Table 有 "Formal Definition" 列，里面有很多带方程的符号，我以前没有遇到过这些符号。任何人都可以熟悉这个吗？ https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann–Landau_notations
定义背后的逻辑其实很简单，它基本上是说无论什么常数乘以结果，从某个点 n 足够大，函数之一将开始成为bigger/smaller 并且一直如此。
为了看到真正的区别，我将解释 small-o（表示某些函数的复杂度低于其他函数），它表示对于所有大于零的 k，您可以找到一些值n 调用了 n_0，其中所有 n 大于 n_0 的都遵循以下模式：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))
在复杂性理论方面，您可以将符号视为 smaller/bigger，因此
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