15

このコード ブロックを作成しましたが、計算に多くの時間を費やしています... 効率的な方法を見つけるのを手伝ってくれませんか?

int tag;
int* factors(int n)
{
    int a[1000000];
    for(int i=1;i<=n/2;i++)
        if(n%i==0)
            a[++tag]=i;
    a[++tag]=n;
    return(a);
}

この強引な方法は、複雑さの点で非常に重いです...この問題に対するより良い実行可能な解決策はありますか?

4

1 に答える 1

10

これまで、これほど高速なアルゴリズムを思いついた人はいません。これは必ずしも何もないことを意味する必要はありません。一方で、はるかに高速に実行することが不可能であることも証明されていません。

考慮したい最適化の 1 つは、sqrt (n) に達したときに停止できる n/2 まで検索する必要がないことです。

...そして、「chris」コメントで既に述べたように、見つかったすべての候補のリストを本当に返したい場合は、番号の別の保存場所を選択してください。

編集：

かなり多種多様なアルゴリズムが利用可能であり、時間の複雑さの点で、あなたが尋ねたものよりも少し速く実行される可能性があると宣伝されていたので、上記の短いコメントよりもいくつかの言葉を追加するように指示されるかもしれません.

最初にループを奇数に分割した後、2 のステップでループを実行するだけで計算時間を節約する最も明白な可能性に加えて、利用可能な他のトリックがまだいくつかありますが、上記の回答では大幅に高速であるとは言及していません.

この決定に至った主な理由は、たとえば、反復回数を 2 分の 1 に削減することは、数の増加に伴う実行時間の予想される増加と比較して、大きな勝利のように見えるためです。定数は非常に小さくなるため、複雑さの理論ではまったく違いがなく、両方のアルゴリズムの時間の複雑さが（ほぼ）同じであると言われます。

元のアルゴリズムのランタイムの数千億倍の一定のゲインを得ることができたとしても、両者の間に違いはまったくありません。

数字が大きいほど、実行時間の観点からプレイをイメージできる限り大きな定数であっても、影響が少なくなります。

時間の複雑さに関する非常に特別な障壁の 1 つは、実際に実行可能か不可能かの境界と見なされることが多い、いわゆるpolynomial実行時間の問題です。

これは、成長に伴って実行時間が大幅に増加する可能性があるとしても、nこの増加を一定の指数kで記述できることを意味していますn^k。

一方、polynomialランタイムのないアルゴリズムは、どれだけ大きくしたいかを指数で測定することはできません。

この違いが実際に問題になる理由の例を示すために、2 つの架空のアルゴリズムを見てみましょう。多項式ランタイムを持つ最初のもの、たとえばn^10、別のものは runtime でこれを言いますn!。

小さい数の場合は悪くないように見えますが、ここで n がちょうど 10 であるとしましょう。アルゴリズム 1 は10^10 = 10000000000時間単位を要しますが、3628800単位のみを使用すると、2 番目のアルゴリズムはさらに高速に実行されるようです。

アルゴリズム 2 の問題点は、アルゴリズム 1 と比較して、ランタイムが劇的に速くなることです。n=100次のようなものが得られます。アルゴリズム1000000000000000000001 の場合は93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000、アルゴリズム 2 の場合と同様です。

フロンティアをさらに押し進めると、次のようになります: アルゴリズム 1 は at で、2 番目のアルゴリズムn=1000は1000000000000000000000000000000402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

信じられないなら、自分で計算してください。マニュアルには階乗関数の実装方法のbc例も含まれています。

しかし、数字を数えながらめまいを起こさないでください...宇宙の年齢を掛ける係数を得るために、10にいくつの末尾のゼロを追加する必要があるかを知ることは興味深いかもしれませんプランク時間の単位で測定したとしても。残念ながらわかりません。

これらすべてについて興味深いのは、因数分解をpolynomial時間内に実行できる既知のアルゴリズムが今日まで存在しないという事実です。

それ自体が興味深い研究分野であるだけでなく、大きな整数を因数分解することは実際には不可能であることも、今日広く使用されている RSA 公開鍵暗号アルゴリズムで重要な役割を果たしているため、ほとんど当然のことながら、すでに多くの研究が行われています。このエリアの中では。

(前述の障壁を破ることなく)想定したアルゴリズムよりもわずかに高速に実行されるアルゴリズムを発見する。

「Jim Balter」は彼のコメントですでに正しく注釈を付けているため、参照記事 ( http://en.wikipedia.org/wiki/Integer_factorization#General-purposeを参照) を参照して、メソッドを確認することをお勧めします。他の人はすでに思いついた。

"Jim" によって言及されたこの記事も、別の興味深いリソースになる可能性があります: (参照:最速の因数分解アルゴリズムとは? )

参照すべきもう 1 つの興味深いリンクは、過去数年間の RSA ファクタリング チャレンジの勝者のリストであり、実現可能とほぼ不可能の境界が現在どこにあるのかをどうにかして把握することができます。( http://en.wikipedia.org/wiki/RSA_Factoring_Challenge )

于 2013-03-29T04:14:18.350 に答える