algorithm - 计算 2^N 个函数的运行时间

Question

对于家庭作业，我被要求计算各种算法的运行时间。难倒我的部分是 2^N，因为 N 的大小是如此之大。

假设一个数据大小为 N=1000 的 2^N 算法需要 5 秒来执行，计算数据大小 {2000, 3000, 10000} 的运行时间

现在，根据指数除法的性质，2^2000/2^1000 = 2^1000。结果是 5.071509e+301 秒在 2000 个项目的数据集上执行。

我怎样才能为接下来的两个尺寸提供一个数字？在我使用的任何计算器中，2^2000 和 2^9000 都返回无穷大。教授的提示是2^10近似于10^3，也就是说1024近似于1000。

Answer 1

时间复杂度的函数是 f(N) = c * 2 ^N。

由于 f(1000) = 5，我们可以求解 c = 5 / 2 ¹⁰⁰⁰。

所以 f(N) = 5 * 2 ^{N - 1000}和 f(k * 1000) = 5 * 2 ^{(k - 1)*1000}。

封锁似乎是计算 2 ⁿ，所以我会指导你。

我将以您的一个示例来演示该方法：

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 ¹⁰⁰⁰的运行时间，在没有 WolframAlpha的情况下很容易确定 2 ^{10000的运行时间：}

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