一般来说，决定算法复杂度在理论上是不可能的。
然而，一种很酷且以代码为中心的方法是实际上直接考虑程序。举个例子：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
现在我们要分析它的复杂性，所以让我们添加一个简单的计数器来计算内线的执行次数：
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
counter++;
}
}
因为 System.out.println 行并不重要，让我们删除它：
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
counter++;
}
}
现在我们只剩下计数器了，我们显然可以简化内部循环：
int counter = 0;
for (int i = 0; i < n; i++) {
counter += n;
}
...因为我们知道增量恰好运行n次。现在我们看到 counter 正好增加了n次，所以我们将其简化为：
int counter = 0;
counter += n * n;
我们出现了（正确的）O（n 2）复杂性:)它在代码中:)
让我们看看递归斐波那契计算器是如何工作的：
int fib(int n) {
if (n < 2) return 1;
return fib(n - 1) + fib(n - 2);
}
更改例程，使其返回其中花费的迭代次数，而不是实际的斐波那契数：
int fib_count(int n) {
if (n < 2) return 1;
return fib_count(n - 1) + fib_count(n - 2);
}
还是斐波那契！:) 所以我们现在知道递归斐波那契计算器的复杂度为 O(F(n))，其中 F 是斐波那契数本身。
好的，让我们看一些更有趣的东西，比如说简单（而且效率低下）的归并排序：
void mergesort(Array a, int from, int to) {
if (from >= to - 1) return;
int m = (from + to) / 2;
/* Recursively sort halves */
mergesort(a, from, m);
mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
}
for (i = from; i < to; i++)
a[i] = b[i - from];
}
因为我们对实际结果不感兴趣，但对复杂性感兴趣，我们更改例程，使其实际返回执行的工作单元数：
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
count++;
}
for (i = from; i < to; i++) {
count++;
a[i] = b[i - from];
}
return count;
}
然后我们删除那些实际上不影响计数的行并简化：
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
count += to - from;
/* Copy the array */
count += to - from;
return count;
}
还是稍微简化一下：
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
count += (to - from) * 2;
return count;
}
我们现在实际上可以省去数组：
int mergesort(int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(from, m);
count += mergesort(m, to);
count += (to - from) * 2;
return count;
}
我们现在可以看到，实际上 from 和 to 的绝对值不再重要，而只是它们的距离，所以我们将其修改为：
int mergesort(int d) {
if (d <= 1) return 1;
int count = 0;
count += mergesort(d / 2);
count += mergesort(d / 2);
count += d * 2;
return count;
}
然后我们得到：
int mergesort(int d) {
if (d <= 1) return 1;
return 2 * mergesort(d / 2) + d * 2;
}
这里显然第一次调用的d是要排序的数组的大小，所以你有复杂度 M(x) 的递归（这在第二行很明显:)
M(x) = 2(M(x/2) + x)
为了获得封闭形式的解决方案，您需要解决这个问题。您可以通过猜测解 M(x) = x log x 来完成此操作，并验证右侧：
2 (x/2 log x/2 + x)
= x log x/2 + 2x
= x (log x - log 2 + 2)
= x (log x - C)
并验证它渐近等价于左侧：
x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x