[解決済み】アルゴリズムの時間複雑性を求めるには？

質問

私は グーグル と スタックオーバーフロー を検索してみましたが、時間の複雑さを計算する方法について明確でわかりやすい説明はどこにもありませんでした。

すでに知っていることは？

下のような簡単なコードで言ってみてください。

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

下のようなループを言う。

for (int i = 0; i < N; i++) {
    Console.Write('Hello World !');
}

• int i=0; のみ実行されます。 一度だけ . に実際に計算される時間です。 i=0 であり、宣言ではありません。
• i < N; これが実行されます N+1 回
• i++ これが実行されます N 回

つまり、このループで必要な操作の回数は {1+(n+1)+n} = 2n+2 . (しかし、私の理解に自信がないので、これはまだ間違っているかもしれません)。

OK、ではこれらの小さな基本的な計算は分かっているつもりですが、ほとんどの場合、時間的な複雑さは O(N), O(n^2), O(log n), O(n!) , そして多くの その他 .

解決方法は？

アルゴリズムの時間計算量の求め方

入力の大きさの関数として実行されるマシン命令の数を加算し、最大（Nが非常に大きいとき）の項に式を単純化し、任意の単純化定数因子を含めることができます。

例えば、次のように簡略化することができます。 2N + 2 という機械語命令で記述します。 O(N) .

なぜ、2つの 2 s ?

Nが大きくなったときのアルゴリズムの性能に興味があります。

2Nと2の2項を考える。

Nが大きくなると、この2つの項の影響力は相対的にどうなるのでしょうか？Nが100万だとする。

そうすると、第1項は200万で、第2項は2しかない。

このため、Nが大きい場合は最大の項以外を削除する。

ということで、今、私たちは 2N + 2 から 2N .

従来、私たちはパフォーマンスのみに関心を寄せていました 定数倍まで .

つまり、Nが大きいときに性能に何らかの定数倍の差があっても、あまり気にならないのです。 そもそも2Nという単位はどうせうまく定義できない。 だから、定数倍したり割ったりして、最も単純な表現にすればいいのです。

そこで 2N は単なる N .