一般に、アルゴリズムの複雑さを決定することは、理論的には不可能です。
ただし、それを行うためのクールでコード中心の方法の 1 つは、実際にはプログラムの観点から直接考えることです。あなたの例を見てください：
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 だけ正確に 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) の繰り返しがあります (これは 2 行目にはっきりと見えます:)
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