至于“如何计算”大O，这是计算复杂性理论的一部分。对于一些(许多)特殊的情况，您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数)，特别是当您想要的只是任何上限估计时，并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。

如果你真的想回答任何算法的问题你能做的最好的就是应用这个理论。除了简单的“最坏情况”分析，我发现平摊分析在实践中非常有用。

不要忘记考虑空间的复杂性，如果内存资源有限，这也是一个值得关注的问题。例如，你可能听到有人想要一个常数空间算法，这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

有时，复杂性可能来自于某个东西被调用了多少次，循环执行的频率，内存分配的频率，等等，这是回答这个问题的另一部分。

最后，大O可以用于最坏情况、最佳情况和摊销情况，其中通常用最坏情况来描述算法可能有多糟糕。

小提示:大O符号是用来表示渐近复杂度的(也就是说，当问题的大小增长到无穷大时)，它隐藏了一个常数。

这意味着在O(n)和O(n2)的算法之间，最快的并不总是第一个算法(尽管总是存在一个值n，这样对于大小为>n的问题，第一个算法是最快的)。

注意，隐藏常数很大程度上取决于实现!

此外，在某些情况下，运行时并不是输入大小为n的确定函数。以快速排序为例:对n个元素的数组进行排序所需的时间不是一个常数，而是取决于数组的初始配置。

有不同的时间复杂度:

最坏的情况(通常是最简单的，但并不总是很有意义) 一般情况下(通常很难弄清楚…) .．.

一个很好的介绍是R. Sedgewick和P. Flajolet的《算法分析导论》。

正如你所说，过早的优化是万恶之源，(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。

我认为，一般来说用处不大，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下界，还有一个Big Theta Θ，它同时定义了上界和下界。

我不知道如何通过编程来解决这个问题，但人们做的第一件事是我们对算法的特定模式进行抽样，比如4n²+ 2n + 1我们有两个规则:

如果我们有一个项的和，增长率最大的项被保留，其他项被省略。 如果我们有几个因数的乘积，常数因数就省略了。

如果我们化简f(x)，其中f(x)是所做操作数量的公式，(上文解释的4n²+ 2n + 1)，我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值，这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西，那么这个算法可能是不可编程的。但如果有人证明我错了，给我代码. . . .

大O符号很有用，因为它很容易使用，并且隐藏了不必要的复杂性和细节(对于一些不必要的定义)。求解分治算法复杂性的一种好方法是树法。假设你有一个带有中值过程的快速排序版本，所以你每次都将数组分割成完美平衡的子数组。

现在，构建一个与所使用的所有数组对应的树。根结点有原始数组，根结点有两个子数组。重复此步骤，直到底部有单个元素数组。

由于我们可以在O(n)时间内找到中位数，并在O(n)时间内将数组分成两部分，因此在每个节点上所做的功为O(k)，其中k是数组的大小。树的每一层都包含(最多)整个数组，所以每层的功是O(n)(子数组的大小加起来是n，因为每层有O(k)，我们可以把它加起来)。树中只有log(n)层，因为每次我们将输入减半。

因此，我们可以将功的上限设为O(n*log(n))。

然而，大O隐藏着一些我们有时不能忽视的细节。考虑计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

假设a和b在Java中是biginteger或者其他可以处理任意大数字的东西。大多数人会毫不犹豫地说这是一个O(n)算法。理由是，在for循环中有n次迭代，而O(1)工作在循环的一侧。

但是斐波那契数列很大，第n个斐波那契数列是n的指数级，所以仅仅是存储它就需要n个字节。对大整数执行加法将花费O(n)个工作量。所以在这个过程中所做的总功是

一加二加三……+ n = n(n-1)/2 = O(n)

所以这个算法在二次时间内运行!