4
私は（mod n）を計算したいと言います。これの時間の複雑さは何ですか？私はMatlabを使用していますが、Matlabがどのように計算しているかわかりません。それをaで分けるか、整数部分を減算し、nで乗算するか？モジュラー算術の時間複雑度
「これの時間の複雑さは何ですか？」と聞くのは意味がありますか？
A
答えて
2
長い数字aおよび/またはnの時間の複雑さについて質問するのは理にかなっています。関連分野は、計算数論と呼ばれます。たとえば、bookを参照してください。
Matlabでよく使用される通常の整数演算は、一定時間内に実行されるALU演算（または複数演算）です。この場合、整数のサイズが制限されていることを覚えておく必要があります。 MATLABのようにMOD（x、y）を算出する助けに内蔵によれば
0
：
MOD（X、Y）= xで - 床（X./Y）* Y
ここ床関数は負の無限大に向かって丸めます（小数部を取り除きます）。
mod（X、y）を計算しない限り、ランタイムは一定です。ここでXはベクトルです。この場合、ベクトルの要素の数と線形にスケーリングされます