大O符号，如何计算或近似计算？

非常好的问题！

免责声明：此答案包含虚假陈述，请参见下面的评论。

如果您正在使用大O符号，那么您正在讨论最坏情况（稍后会详细说明）。此外，平均情况有大写Theta，而最佳情况则有大Omega。

请查看此网站以获取有关大O的可爱正式定义：https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n))意味着存在正常数c和k，使得对于所有n≥k，0≤f(n)≤cg(n)。 c和k的值必须固定为函数f，不能取决于n。

---

那么现在我们所说的“最佳情况”和“最坏情况”复杂性是什么意思？

这可能是通过示例最清楚地说明的。例如，如果我们使用线性搜索在排序数组中查找数字，则最坏情况是当我们决定搜索数组的最后一个元素时，因为这将需要与数组中的项目一样多的步骤。 最佳情况是当我们搜索第一个元素时，因为我们在第一次检查后就完成了。

所有这些形容词-情况的复杂性的重点是，我们正在寻找一种以特定变量的大小来衡量假设程序运行完成所需时间的方法。然而，对于许多算法，您可以认为不存在特定输入的单个时间。请注意，这与函数的基本要求相矛盾，即任何输入都不应具有多于一个输出。因此，我们提出了多个函数来描述算法的复杂性。现在，即使在大小为n的数组中搜索可能需要根据您在数组中寻找什么以及与n成比例地取决于n而变化，我们仍然可以使用最佳情况、平均情况和最坏情况类别创建有关算法的信息性描述。

很抱歉，这篇文章写得很差，缺乏技术信息。但是希望它能让时间复杂度类更易于思考。一旦您熟悉了这些内容，就可以简单地解析程序并查找依赖于数组大小的for循环等内容，并根据数据结构推理出哪种输入会导致琐碎的情况，哪种输入会导致最坏情况。

经常被忽视的是算法的预期行为。这并不改变您算法的大O，但它与“过早优化”的说法有关。
算法的预期行为是指您可以预计在最可能看到的数据上，您的算法能够工作得有多快，非常简化地说。
例如，如果您正在搜索列表中的值，则为O(n)，但如果您知道大多数列表都将您的值放在前面，则算法的典型行为会更快。
要真正理解它，您需要能够描述“输入空间”的概率分布（如果您需要对列表进行排序，那么该列表已经排序的频率是多少？它完全反转的频率是多少？它大多数时候是排序的吗？）你不总是能够知道，但有时你确实知道。

对于代码A，外部循环将执行n+1次，其中第一次是检查i是否仍符合要求的过程。内部循环运行n次，n-2次...因此，0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。
对于代码B，虽然内部循环不会进入并执行foo()，但内部循环将根据外部循环执行时间执行n次，即O(n)。

我不知道如何通过编程解决这个问题，但人们通常的第一步是对算法进行采样，以确定操作次数中的某些模式，如4n^2 + 2n + 1，我们有两条规则：

1. 如果我们有多项式之和，则保留增长率最大的项，并省略其他项。
   
2. 如果我们有多个因素的积，则省略常数因子。

如果我们简化f(x)，其中f(x)是操作次数的公式（上面解释了4n^2 + 2n + 1），我们可以得到大O值[在这种情况下为O(n^2)]。但是，这将需要考虑程序中的拉格朗日插值，这可能难以实现。如果真正的大O值是O(2^n)，并且我们可能会有像O(x^n)这样的东西，那么这个算法可能就无法编写。但是如果有人证明我错了，请给我代码。