大多数拥有计算机科学学位的人肯定知道大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)。对于函数f, c和k的值必须是固定的，且不依赖于n。
好的，那么我们所说的"最佳情况"和"最坏情况"是什么意思呢?
这一点可以通过例子得到最清楚的说明。例如，如果我们使用线性搜索在一个排序数组中查找一个数字，那么最坏的情况是我们决定搜索数组的最后一个元素，因为这将花费与数组中有多少项一样多的步骤。最好的情况是当我们搜索第一个元素时，因为我们将在第一次检查之后完成。
The point of all these adjective-case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.
抱歉，这是如此糟糕的写作和缺乏太多的技术信息。但希望这能让时间复杂度类更容易理解。一旦你熟悉了这些，你就可以很简单地解析你的程序，寻找像for-loops这样依赖于数组大小的东西，并根据你的数据结构推理什么样的输入会导致简单的情况，什么样的输入会导致最坏的情况。
其他回答
基本上90%的情况下都是分析循环。你有单、双、三重嵌套循环吗?你有O(n) O(n²)O(n³)的运行时间。
很少(除非你正在编写一个具有广泛基库的平台(例如，.NET BCL或c++的STL)，你会遇到比查看循环(for语句，while, goto等…)更困难的事情。
对于代码A，外层循环将执行n+1次，“1”时间表示检查i是否仍然满足要求的过程。内循环运行n次，n-2次....因此，0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。
对于代码B，虽然内部循环不会介入并执行foo()，但内部循环将执行n次，这取决于外部循环的执行时间，即O(n)
虽然知道如何计算出特定问题的大O时间是有用的，但了解一些一般情况可以在很大程度上帮助您在算法中做出决策。
以下是一些最常见的案例，摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:
O(1) -确定一个数字是偶数还是奇数;使用常量大小的查找表或哈希表
O(logn) -用二分搜索在排序数组中查找一个项
O(n) -在未排序的列表中查找一个项;两个n位数相加
O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序
O(n3) -用简单的算法乘以两个n×n矩阵
O(cn) -使用动态规划找到旅行商问题的(精确)解;使用蛮力判断两个逻辑语句是否等效
O(n!) -通过暴力搜索解决旅行推销员问题
O(nn) -通常用来代替O(n!)来推导更简单的渐近复杂度公式
如果您希望根据经验而不是通过分析代码来估计代码的顺序，您可以插入一系列不断增加的n值，并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n)，值应该落在斜率为n的直线上。
这比只研究代码有几个优点。首先，您可以看到您是否在运行时接近其渐近顺序的范围内。此外，您可能会发现一些您认为是O(x)阶的代码实际上是O(x^2)阶的代码，例如，因为花在库调用上的时间。
看到这里的答案，我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序，而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多，我必须补充一点，即使教授也鼓励我们(后来)实际思考，而不是仅仅计算。
我还想补充一下如何对递归函数进行处理:
假设我们有这样一个函数(scheme code):
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
递归地计算给定数字的阶乘。
第一步是尝试并确定函数体的性能特征，只是在这种情况下，在函数体中没有做任何特殊的事情，只是一个乘法(或返回值1)。
所以主体的性能是:O(1)(常数)。
接下来尝试确定递归调用的数量。在这种情况下，我们有n-1个递归调用。
所以递归调用的性能是:O(n-1)(阶为n，因为我们抛弃了无关紧要的部分)。
然后把这两个放在一起，你就得到了整个递归函数的性能:
1 * (n-1) = O(n)
Peter, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an approximation and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example. Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.
