英文:
What is Big O of n^2 x logn?
问题
n^2 x logn 或者 n^3？我知道这两个答案都作为上界，我只是在选择更紧密但更复杂的界限（选项1）和更“糟糕”但更简单的界限（选项2）之间犹豫不决。
关于大O函数是否有一般规则，比如大O函数永远不会太复杂或是两个函数的乘积吗？
英文:
Is it n^2 x logn or n^3? I know both of these answers act as upper bounds, I’m just torn between choosing a tighter but more complex bound (option 1), or a “worse” yet simpler bound (option 2).
Are there general rules to big O functions such as big O functions can never be too complex/a product of two functions?
答案1
得分: 2
你已经似乎非常了解大O表示法是一个上界的事实，以及具有运行时复杂度 n^2 logn 的函数同时属于 O(n^2 logn) 和 O(n^3)，所以我会省略掉这方面的数学。从 n^2 logn 属于 O(n^3) 这一事实立刻可以看出，O(n^2 logn) 是 O(n^3) 的子集，因此前者至少是一个很好的界限。事实证明它是一个严格更紧的界限（通过一些基本代数可以看出），这是一个明显的优点。我理解你对界限复杂性的担忧，但我不会担心这个。在数学上，当精度与简单性相冲突时，最好选择精度，而 n^2 logn 不是一个那么复杂的表达式。所以在我看来，O(n^2 logn) 是一个更好的界限来陈述。
其他类似或更复杂的例子：
- 正如评论中所指出的，归并排序 和 快速排序 的平均时间复杂度为
O(n logn)。 - 插值搜索 的平均时间复杂度为
O(log logn)。 - Dijkstra算法的平均情况被陈述在维基百科上为绕口令般的
O(E + V log(E/V) log(V))。
英文:
You already seem to have an excellent understanding of the fact that big-O notation is an upper bound, and also that a function with runtime complexity n^2 logn falls in both O(n^2 logn) and O(n^3), so I'll spare you the mathematics of that. It's immediately clear (from the fact that n^2 logn is in O(n^3)) that O(n^2 logn) is a subset of O(n^3), so the former is a at least as good of a bound. It turns out to be a strictly tighter bound (that can be seen with some basic algebra), which is a definite point in its favor. I do understand your concern about the complexity of bounds, but I wouldn't worry about that. Mathematically, it's best to favor accuracy over simplicity, when the two are at odds, and n^2 logn is not that complex of an expression. So in my mind, O(n^2 logn) is a much better bound to state.
Other examples of similar or greater complexity:
- As indicated in the comments, merge sort and quicksort have average time complexity
O(n logn). - Interpolation search has an average time complexity of
O(log logn). - The average case of Dijkstra's algorithm is stated on Wikipedia to be the absolute mouthful
O(E + V log(E/V) log(V)).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论