算法复杂度如何计算？

Question

今天我在看文章的时候，里面有一句话提到“算法复杂度达到 O(n^3)，其中 n 是树中节点的总数”，那么这个大O是什么意思呢？O(n^3)这个复杂度是什么概念？

Answer 1

这里的O就是一般表示复杂度的一个标志，类似计算复杂度的函数名称一样。

复杂度一般分为空间复杂度和时间复杂度。
空间复杂度是指算法在运算过程中对内存空间占用的最大值。
时间复杂度是指算法在运算过程中对最大消耗的时间。

两种复杂度都是一种估算，
估算的方式就是根据代码的逻辑，分析出对于复杂度的公式。

在时间复杂度上，主要记录的是带有变量的循环。
比如for (i = 0; i < n; i ++) {...}可理解为O(n)
而 x = n + 1; y = x + 1; z = x + y;虽然是三条语句，但是没有循环操作，所以理解为O(1)

在空间复杂度上，主要记录的是带有变量的空间申请。
比如int[n] x;可以理解为O(n)
而 int x; int y; int z;虽然是三个变量，但是没有变化的申请操作，所以理解为O(1)

Answer 2

建議你先懂big-O的數學定義喔
Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Answer 3

O--同阶

n表示问题的规模，要处理的对象的数目。O(n^3)表示，随着问题规模n的增长，执行的计算规模呈k(n^3)+b的形式增长。b是常数，在公式化到最简的情况下，k是与n无关的系数。（精确的说法早就忘了，求轻拍）

往最具体的说，三重嵌套循环，最里层有一个计算语句，每个循环传进来的循环次数都是n,那么随着n的增长，这个计算语句被执行的次数呈n的三次方增长。

而同阶的意思是，可能呈 5n^3的形式增长，具体次数可能是5n^3+2,(比如把上面的嵌套循环写成一个函数，调用5次，另外再加两个固定的计算语句)，但不管如何，它们都是n^3的同阶。这个同阶的概念来自于微积分的无穷大和无穷小，参考高等数学教材。

Answer 4

我的理解个人（）：复杂度就是你执行了多少次基础运算，n是规模，n的三次方最简单的情况就是三重嵌套循环。判断方法是去log然后向下取整。一次两次三次 就都是O1 1n 2n 3n 都是On.