最大公約数を見つけるための線形時間アルゴリズム

私はいくつかの研究を行っており、実行時間が0(N)以上のアルゴリズムがいくつか見つかりました。誰かが最大公約数を見つけるための線形時間アルゴリズムを知っているのであれば、私は興味がありますか？最大公約数を見つけるための線形時間アルゴリズム

この場合、「N」の意味は何ですか？最大の数字の（バイナリ）数字の数？また、ドメインとは何ですか？ほとんどのGCDアルゴリズムはどこかで分割を使用し、64ビット整数の除算は 'O（1） 'ですが、任意の精度の整数は少なくとも' O（n）'です。 –

O（（n log n）^ 2）アルゴリズムが見つかりました。私はまた、実際のランタイムが何であるかは分かりませんでしたが、それが線形ではないことを確信していました。 –

@ElianEbbing：申し訳ありませんが、この場合、私は整数にしか関心がありません。 Nは最大の整数です。 –

まだ存在しない場合は、 Wikipediaから;

最もよく知られた決定論的アルゴリズムは N1 +εプロセッサと時間をO（N /ログN）における問題を解決することができる（CRCW-PRAMモデルにおける）チョーとGoldreich、によるものです。

2012-03-13 18:24:40

答えて