Как правило, определение сложности алгоритма теоретически невозможно.
Тем не менее, один классный и ориентированный на код метод для этого состоит в том, чтобы на самом деле просто мыслить непосредственно в терминах программ. Возьмите свой пример:
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 точно 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;
}
Теперь мы можем видеть, что на самом деле абсолютные значения от и до уже не имеют значения, а только их расстояние, поэтому мы изменим это на:
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