algorithm - 2^N 関数の実行時間の計算

Question

宿題で、さまざまなアルゴリズムの実行時間を計算するように求められました。N のサイズが非常に大きいため、私を悩ませているのは 2^N です。

データ サイズ N=1000 の 2^N アルゴリズムの実行に 5 秒かかると仮定して、データ サイズ {2000, 3000, 10000} のランタイムを計算します。

さて、指数除算の性質より 2^2000/2^1000 = 2^1000 です。結果は、2000 項目のデータ セットで実行するのに 5.071509e+301 秒です。

次の 2 つのサイズの番号を指定するにはどうすればよいですか? 2^2000 と 2^9000 はどちらも、私が使用する電卓では無限大を返します。教授のヒントは、2^10 は 10^3 に近似し、1024 は 1000 に近似するということです。

Answer 1

時間計算量の関数は f(N) = c * 2 ^Nです。

^{f(1000) = 5 なので、c = 5 / 2 1000}を解くことができます。

したがって、 f(N) = 5 * 2 ^{N - 1000}、および f(k * 1000) = 5 * 2 ^{(k - 1)*1000}です。

^{封鎖は 2 n}を計算して行うようですので、これについてご案内します。

メソッドを示すために、あなたの例の1つを取り上げます。

2 ¹⁰⁰⁰ = 2 ^{10 * 100} = (2 ¹⁰ ) ¹⁰⁰ ≈ (10 ³ ) ¹⁰⁰ = 10 ^{3 * 100} = 10 ³⁰⁰ = 1e300

それはあなたの先生のヒントを使用しています。数値をより正確に計算する別の方法は次のとおりです。

2 ¹⁰⁰⁰ = 10 ^{1000 * ログ₁₀ 2} = 10 ^301.03 = 10 ^0.03 * 10 ³⁰¹ = 1.0715e301

（ご覧のとおり、より正確な方法は、近似方法の結果よりも 10.7 倍多くなります）

Answer 2

明らかに、あなたは WolframAlpha を試していません:

2^9000 = 1861919823602446870051646947443265806218680881620164150161309755333181392347475969737916885903925979688282376725245050928552019850699830936678289110574564545897808148390669479768088103164174862614314896361751492419355200744919106773071079582599147802839706215610874713577461171484389014531465527630202236883843662826326484204605969450292309212479576754101484210438029392847117393209646612418243468945316443055403112189769994194382253211069075682210324665380367163398351260390065146550963353638226230571087153090476005831034463871223599543367440127371321307935600294235235555686651194174520755709233252147269712646152398661272615394330256766919854213808655136454478279520538925315159120689449046824765276993871084725126289174642261134186532952389529497451225294280309592333118547431857834022107299493307642886550035108349812538868548204110949267007844894921304724439232280030484032946555862021618822463975371563390466476093942333021906014621095132521668771544547398222309222385454252810109269995041305909748903485123565191403462125774254093965366838199092942669763234497755795922782368415391408328615941087687168142703569478330639528167193433105543630476588701348505543567751790789117717660152741734303989082897740369036292716627460893145378475903236426283709902853825833522685221030263417298462852391838147572583018386475574242223720125609852369550108535609838296845885540331405153336504029657425852682616998765068978970510668576704757343969900471616618487531217423608126248306049345412199702325217046285213249285846153975313978242675003402962824121160875928608618335006217051712260195130737083017631349816669929159176667868417353866905513835554999462637481342721400975639504482716709384155856026263304270260886740810287158032302083388891446551907198669473320114371718138443660594911466234734942910722449045244457975320043694169261701681656148362205170532994281152576853709669767416127252738437485793910219846836498268031157261792859230067295449184914230926461991700842371010236588596679342492743911615365711320743215987995901101163306076544568626531198809370907612331483471833845958618077480217892890533116603350040147116218227928732817945323636422047507156427135297222275812678187736036773320854938458989641651199078792658709405149957007882875374868180442468709128120647047303125901843060904208622152998500617510802742432155144605848971282208131749602408191808406410632175265171306237793956570406435402345476628467209068729893134433124291187516075267594298323098487990166243403468912628117388443154921474663149036640983804471509564893426039130480070632369458141251485052936042164865777219873983089572387511794739572152294019631222145910901210840561445507713655658889336373566800391206925212386456974315749376

ヒントは：

2 ⁹⁰⁰⁰ = (2 ¹⁰ ) ⁹⁰⁰ ≒ (10 ³ ) ⁹⁰⁰ = 10 ²⁷⁰⁰

^{2 1000}の実行時間を知っていることを考えると、WolframAlpha なしで 2 ¹⁰⁰⁰⁰の実行時間を簡単に決定できます。

2 ¹⁰⁰⁰ => 5 秒
2 ¹⁰⁰⁰⁰ = 2 ¹⁰⁰⁰ *2 ⁹⁰⁰⁰ => 5*2 ⁹⁰⁰⁰秒