論理グラフで動作する 2 つのアルゴリズム A と B があり、それらの効率を時間的に比較したいと思います。
両方のアルゴリズムの時間計算量を計算すると、次のことがわかりました。
Time Complexity of A: O(2*n*n)
Time Complexity of B: O((n*n)/2)
ウィキペディア ( http://en.wikipedia.org/wiki/Time_complexity ) によると 、時間計算量を計算するときに係数を無視すると、次の結果が得られます。
Time Complexity of A: O(n^2)
Time Complexity of B: O(n^2)
私が行った 2 番目のステップは、各アルゴリズムがさまざまなサイズのグラフにかかる時間を実験的に計算することです。以下では、x 軸はグラフ内のノードの数を表し、y 軸は時間 (秒) を表します。
ご覧のとおり、大きなグラフの 2 つのアルゴリズムには大きな違いがあります。私の質問は次のとおりです。これは合理的ですか? 同じ時間の複雑さを持つ 2 つのアルゴリズムを持つことは可能ですが、実際には時間に大きな違いがありますか? ありがとうございました。