总的来说，决定算法复杂度在理论上是不可能的。
然而，一种酷炫且以代码为中心的方法是直接按程序思考。以您的示例为例：
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次。现在我们看到计数器会准确地增加
n次，所以我们可以简化成：
int counter = 0;
counter += n * n;
我们已经得出了（正确的）O(n2)时间复杂度 :) 它在代码中呈现出来了 :)
现在让我们看一下递归斐波那契计算器的工作原理：
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;
mergesort(a, from, m);
mergesort(m, m, to);
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;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
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;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
count += to - from;
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
x log x
