25/07/30 15:55:46.79 gxsH3v1Z.net
>>579
データが大きくても係数の差が次数の差より影響することは普通にありえる
キャッシュミスしまくるがO(n)で済むアルゴリズムと
ほぼキャッシュヒットしまくるがO(n·log(n))かかるアルゴリズムがあるとしよう
両者のアルゴリズム自体の係数差は単純にnとn·log2(n)とする
例えばn＝2^30≒10億の場合はアルゴリズムの差でlog2(2^30)＝30倍の差が生じる
ところがキャッシュミスするとメモリアクセスの差で300倍遅いことが現代のCPUでありえる
そのためキャッシュミスしまくるO(n)よりもO(n·log(n))が速く実行されることが起きる