低阶术语在大O表示法中的作用 [英] Role of lower order terms in big O notation

问题描述

以大O表示法，我们总是说在大多数情况下我们应该忽略常数因素.也就是说，而不是写作，

In big O notation, we always say that we should ignore constant factors for most cases. That is, rather than writing,

3n ^ 2-100n + 6

3n^2-100n+6

我们几乎总是很满意

n ^ 2

因为该术语是方程式中增长最快的术语.

since that term is the fastest growing term in the equation.

但是我发现许多算法课程开始比较具有许多术语的函数

But I found many algorithm courses starts comparing functions with many terms

2n ^ 2 + 120n + 5 = n的大O ^ 2

2n^2+120n+5 = big O of n^2

然后为那些长函数找到c和n0，然后建议最后忽略低阶项.

then finding c and n0 for those long functions, before recommending to ignore low order terms in the end.

我的问题是，尝试用许多术语来理解和分析这类功能会得到什么?在本月之前，我很容易理解O(1)，O(n)，O(LOG(n))，O(N ^ 3)的含义.但是，如果我仅依靠此常用功能，是否会错过一些重要概念?如果我跳过对那些长函数的分析，会错过什么?

My question is what would I get from trying to understand and annalising these kinds of functions with many terms? Before this month I am comfortable with understanding what O(1), O(n), O(LOG(n)), O(N^3) mean. But am I missing some important concepts if I just rely on this typically used functions? What will I miss if I skipped analysing those long functions?

推荐答案

您的工作中是否有中间步骤?这就是可能的情况，例如，当您计算一个大O时，您可能不确定是否知道最高阶项，因此您要跟踪所有这些项，然后确定最终哪个复杂度类别有意义.要理解为什么可以忽略低阶术语，还有一些要说的话.

Ever have intermediate steps in your work? That is what this likely is as when you are computing a big O, chances are you don't already know for sure what the highest order term is and thus you keep track of them all and then determine which complexity class makes sense in the end. There is also something to be said for understanding why the lower order terms can be ignored.

采用一些图算法，例如最小生成树或最短路径.现在，仅查看一种算法，您是否知道最高期限将是什么?我知道我不会，所以我会跟踪算法并收集一堆术语.

Take some graph algorithms like a minimum spanning tree or shortest path. Now, can just looking at an algorithm you know what the highest term will be? I know I wouldn't and so I'd trace through the algorithm and collect a bunch of terms.

如果需要另一个示例，请考虑排序算法以及是否要记住所有复杂性.气泡排序，壳排序，合并排序，快速排序，基数排序和堆排序是其中一些较常见的算法.如果您知道如何跟踪算法，则可以既记住算法又考虑复杂性，也可以只记住算法，然后从伪代码中导出复杂性.

If you want another example, consider Sorting Algorithms and whether you want to memorize all the complexities or not. Bubble Sort, Shell Sort, Merge Sort, Quick Sort, Radix Sort and Heap Sort are a few of the more common algorithms out there. You could either memorize both the algorithm and complexity or just the algorithm and derive the complexity from the pseudo code if you know how to trace them.

这篇关于低阶术语在大O表示法中的作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！