2

こんにちは、s = O(logN) であり、Random_Integer の実行時間は一定時間であるという次の仮定で、このアルゴリズムの実行時間を見つけるのに問題があります。

  1  express N-1 as 2^t * u where u is odd:
  2  for i <-- to s do
  3    a <-- Random_Integer(2, N-2);
  4    if EuclidGCD(a, N) not equal to 1 then
  5         return false;
  6    x sub 0 <-- a^u mod N;
  7    for j <-- 1 to t do
  8        x sub j <-- x^2 sub j-1 mod N;
  9    if x sub j = 1 and x sub j-1 not equal to 1 and x sub j-1 not equal to N -1 then
  10        return false;
  11   if x sub t not equal to one then
  12        return false;
  13 return true;

内側のループから始めて、指数モジュラス演算には n^3 時間がかかり、ループは n 回実行され、合計 n^4 になります。次に、外側のループに進みます。再び n^3 時間かかる別の指数モジュラス操作があり、EuclidGCD も n^3 時間かかります。最後に、外側のループも n 回繰り返し実行されます。これらの値は正しいと思いますが、合計実行時間をどのように取得するかについて混乱しています。また、これら 2 つのネストされたループの実行時間を乗算する必要があるかどうか、および外側のループ内の ExtendedEuclid のメソッド呼び出しを外側のループの実行時間で乗算する必要があるかどうかについても混乱しています。これが明確であることを願っています。

4

1 に答える 1

1

内側のループは n^4 (外側のループ内で最も遅い部分) であり、外側のループの反復ごとに 1 回実行されます。これは EDIT: logn 回、つまり n^4logn です。

でも...

早期に到達する頻度によってreturn falseは、最悪の場合でも n^5 になる可能性があります。たとえば、最初の反復でほぼ常に false を返す場合、n^3-n^4 の作業しか費やしていません。したがって、代わりに平均 O(n^3) または O(n^4) (どちらであるreturn falseかに応じて) になります。

于 2013-02-09T08:34:56.600 に答える