证明了大-theta和其他渐近定义(Big，Big，Big，definitions，)

Question

所以在未来的作业中，我注意到了一些问题，要求我们“使用”这些规则。我想知道对于小θ和小omega是否有任何规则(当x接近f(X)/g(X)的无穷大时使用极限)。

此外，对这些规则是否有任何正式的证明？我已经为其中的几个(大-O，小θ，小-欧米加)写了证明。但我和其他人有麻烦--也就是此刻，大欧米茄。我使用极限比率，然后用形式极限的定义来转换，然后应用渐近符号的定义。

所以我看到了这篇文章：https://math.stackexchange.com/questions/925053/using-limits-to-determine-big-o-big-omega-and-big-theta

http://aofa.cs.princeton.edu/lectures/lectures13/AA01-AofA.pdf

Answer 1

这里提供了不涉及限制的定义：

大O

F= O(g)当且仅当存在n0，c>0使得对于n >= n0，f(n) < c*g(n)。

大欧米茄

F= Omega(g)当且仅当g= O(f)。

大Theta

F= Theta(g)当且仅当f= O(g)和f= Omega(g)。

小奥

F= o(g)当且仅当所有c>0存在n0，使得对于n >= n0，f(n) < c*g(n)

小欧米茄

F= omega(g)当且仅当g= o(f)

没有“小θ”。您还可以找到定义为"O \ Theta“和"Omega \ Theta”的"Little o“和"Little omega”；这些定义可以通过显示它们描述的集合相等(即o是O\ Theta的子集，O\Theta是O的子集)来证明等价。

Answer 2

你可以用极限来解小欧米茄和小O。没有小θ。这是一个视频，展示了如何解决大O，大Theta，大欧米茄，小O和小欧米茄https://www.youtube.com/watch?v=QhpfLwe-ERM

​

​