私はすぐにそれを尋ねようとします：
私は関数としてアルゴリズムを持っています。それを呼び出しましょうf:
void f(int[1..N]) {
// algorithm goes here
}
これで、入力real runtime用の がありNます。
time()関数が現在のシステムの時間をミリ秒単位で返すと仮定してください。
int[1...N] n;
unsigned long start = time(), end;
f(N);
end = time();
printf("Real runtime: %ul", end - start);
つまり、f引数が何ミリ秒かかるかを知っていますN。
この情報によって、f(N)実行時の複雑さをどのように計算できf = O(N)ますか?
異なる N に対して複数のデータ ポイントが必要になります。
これらの統計を取得するとしましょう:
N time(ms)
4 12
8 24
16 48
この場合、N を 2 倍にすると時間が 2 倍になるため、複雑さは O(N) でなければなりません。
しかし、これらの統計を取得すると、
N time(ms)
4 16
8 64
16 256
この場合、n を 2 倍にすると実行時間が 4 倍になるため、複雑さは O(n2) になります。
時間がまったく変わらない場合、複雑さは O(1) です
同様に、さまざまなデータ ポイントにより、big(O) を満たす関数を決定できます。異なる N のポイントが多いほど、その関数をより適切に決定できます。