大O表示算法时间复杂度的上界。它通常与处理数据集(列表)一起使用，但也可以在其他地方使用。

下面是一些在C代码中如何使用它的例子。

假设我们有一个n个元素的数组

int array[n];

如果我们想要访问数组的第一个元素，这将是O(1)因为不管数组有多大，它总是需要相同的常数时间来获得第一项。

x = array[0];

如果我们想在列表中找到一个数字:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这是O(n)因为我们最多要遍历整个列表才能找到我们要的数。大O仍然是O(n)，即使我们可能在第一次尝试中找到我们的数字并运行一次循环，因为大O描述了算法的上界(omega是下界，theta是紧界)。

当我们讲到嵌套循环时:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是O(n²)因为对于外层循环的每一次循环(O(n))我们都必须再次遍历整个列表，所以n乘以后只剩下n²。

这仅仅是触及表面，但当你分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。希望这至少能让你熟悉基本知识。

熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于，当您调用一个库函数时，可能会多次调用—您常常不确定是否在不必要的时候调用了函数，或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量，无论是大O还是其他度量，都可以在文档或智能感知中得到。

将算法分解成你知道的大O符号，并通过大O运算符组合。这是我知道的唯一办法。

欲了解更多信息，请查看有关该主题的维基百科页面。

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

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

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

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

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

有不同的时间复杂度:

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

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

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

经常被忽视的是算法的预期行为。它不会改变你的算法的大o，但它确实与“过早优化.. ..”的声明有关

你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。

例如，如果你在一个列表中搜索一个值，它是O(n)，但如果你知道你看到的大多数列表都有你的值在前面，你的算法的典型行为会更快。

为了真正确定它，你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序，这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的，但有时你知道。