私は経験しましたグーグルそしてスタックオーバーフロー検索してみましたが、時間の複雑さを計算する方法についての明確でわかりやすい説明はどこにも見つかりませんでした。
私がすでに知っていることは何ですか?
以下のような単純なコードがあるとします。
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です。(ただし、私の理解に自信がないため、これはまだ間違っている可能性があります。)
さて、これらの小さな基本的な計算は知っていると思いますが、ほとんどの場合、時間計算量はO(N)、O(n^2)、O(log n)、O(n!)、そしてその他多数。
ベストアンサー1
アルゴリズムの時間計算量を調べる方法
入力のサイズの関数として実行されるマシン命令の数を合計し、式を最大の項（N が非常に大きい場合）に簡略化し、簡略化する定数係数を含めることができます。
たとえば、2N + 2機械命令を簡略化して、これを と記述する方法を見てみましょうO(N)。
なぜ 2 つの2s を削除するのでしょうか?
N が大きくなるにつれてアルゴリズムのパフォーマンスがどうなるかに興味があります。
2N と 2 という 2 つの項を考えます。
N が大きくなるにつれて、これら 2 つの項の相対的な影響はどうなるでしょうか。N が 100 万であると仮定します。
すると、最初の項は 200 万になり、2 番目の項は 2 だけになります。
このため、N が大きい場合は、最大の項以外はすべて削除します。
つまり、 から に移行したことになり2N + 2ます2N。
伝統的に、私たちは定数倍までのパフォーマンスにのみ関心があります。
これは、N が大きいときにパフォーマンスに一定の倍数の差があっても、実際には気にしないことを意味します。そもそも 2N の単位は明確に定義されていません。したがって、定数係数を乗算または除算して、最も単純な式を得ることができます。
したがって、2NになりますN。