让我们考虑一下经典的大 O 表示法定义 (证明链接 http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf):
O(f(n))是存在正常数的所有函数的集合C and n0 with |g(n)| ≤ C * f(n)， 对全部n ≥ n_0.
根据此定义，执行以下操作是合法的（g1 and g2是描述两种算法复杂性的函数）：
g1(n) = 9999 * n^2 + n ∈ O(9999 * n^2)
g2(n) = 5 * n^2 + N ∈ O(5 * n^2)
将函数注释为以下形式也是合法的：
g1(n) = 9999 * N^2 + N ∈ O(n^2)
g2(n) = 5 * N^2 + N ∈ O(n^2)
正如你所看到的第一个变体O(9999*N^2) vs (5*N^2)更加精确，让我们清楚地知道哪种算法更快。第二个没有向我们展示任何东西。
问题是：为什么没有人使用第一个变体？
使用O()从一开始，符号就与“精确地”记录某事相反。其想法是掩盖算法之间的“精确”差异，并且能够忽略计算硬件细节以及编译器或编程语言选择的影响。的确，g_1(n) and g_2(n)都在同一个class（或集合）的函数n- 班上O(n^2)。它们在细节上有所不同，但它们足够相似。
事实上，这是一门课，这就是为什么我编辑了你的问题并更正了符号= O(9999 * N^2) to ∈ O(9999 * N^2).
顺便说一句 - 我相信你的问题更适合cs.stackexchange.com http://cs.stackexchange.com.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
