Calculando o tempo de execução de funções 2 ^ N - algoritmo

Para uma tarefa de casa, me pediram para calcular o tempo de execução de vários algoritmos. A parte que está me atrapalhando é o 2 ^ N, porque o tamanho de N é muito grande.

Assumindo que um algoritmo 2 ^ N com um tamanho de dados N = 1000 leva 5 segundos para ser executado, calcule o tempo de execução para tamanhos de dados {2000, 3000, 10000}

Agora, 2 ^ 2000/2 ^ 1000 = 2 ^ 1000 pela propriedade da divisão expoente. O resultado é 5.071509e + 301 segundos para executar em um conjunto de dados de 2.000 itens.

Como posso dar um número para os próximos dois tamanhos? 2 ^ 2000 e 2 ^ 9000 retornam o infinito em qualquer calculadora que eu use. Os professores sugerem que 2 ^ 10 é aproximadamente 10 ^ 3, o que significa que 1024 é aproximadamente 1000.

Respostas:

1 para resposta № 1

A função da complexidade do tempo é f (N) = c * 2^N.

Desde f (1000) = 5, podemos resolver para c = 5/2¹⁰⁰⁰.

Então f (N) = 5 * 2^{N - 1000}e f (k * 1000) = 5 * 2^{(k - 1) * 1000}.

O bloqueio parece ser com o cálculo 2ⁿ, então eu irei te guiar nisto.

Vou tomar um de seu exemplo para demonstrar o método:

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

Isso é usando a dica do seu professor, outra maneira de calcular o número com mais precisão é:

2¹⁰⁰⁰ = 10^{1000 * log₁₀2} = 10^301.03 = 10^0.03 * 10³⁰¹ = 1,0715e301

(Como você pode ver, o método mais preciso será 10.7 vezes mais que o resultado do método aproximado)

---

1 para resposta № 2

Obviamente, você não tentou o WolframAlpha:

2^9000 = 1861919823602446870051646947443265806218680881620164150161309755333181392347475969737916885903925979688282376725245050928552019850699830936678289110574564545897808148390669479768088103164174862614314896361751492419355200744919106773071079582599147802839706215610874713577461171484389014531465527630202236883843662826326484204605969450292309212479576754101484210438029392847117393209646612418243468945316443055403112189769994194382253211069075682210324665380367163398351260390065146550963353638226230571087153090476005831034463871223599543367440127371321307935600294235235555686651194174520755709233252147269712646152398661272615394330256766919854213808655136454478279520538925315159120689449046824765276993871084725126289174642261134186532952389529497451225294280309592333118547431857834022107299493307642886550035108349812538868548204110949267007844894921304724439232280030484032946555862021618822463975371563390466476093942333021906014621095132521668771544547398222309222385454252810109269995041305909748903485123565191403462125774254093965366838199092942669763234497755795922782368415391408328615941087687168142703569478330639528167193433105543630476588701348505543567751790789117717660152741734303989082897740369036292716627460893145378475903236426283709902853825833522685221030263417298462852391838147572583018386475574242223720125609852369550108535609838296845885540331405153336504029657425852682616998765068978970510668576704757343969900471616618487531217423608126248306049345412199702325217046285213249285846153975313978242675003402962824121160875928608618335006217051712260195130737083017631349816669929159176667868417353866905513835554999462637481342721400975639504482716709384155856026263304270260886740810287158032302083388891446551907198669473320114371718138443660594911466234734942910722449045244457975320043694169261701681656148362205170532994281152576853709669767416127252738437485793910219846836498268031157261792859230067295449184914230926461991700842371010236588596679342492743911615365711320743215987995901101163306076544568626531198809370907612331483471833845958618077480217892890533116603350040147116218227928732817945323636422047507156427135297222275812678187736036773320854938458989641651199078792658709405149957007882875374868180442468709128120647047303125901843060904208622152998500617510802742432155144605848971282208131749602408191808406410632175265171306237793956570406435402345476628467209068729893134433124291187516075267594298323098487990166243403468912628117388443154921474663149036640983804471509564893426039130480070632369458141251485052936042164865777219873983089572387511794739572152294019631222145910901210840561445507713655658889336373566800391206925212386456974315749376

Quanto à dica:

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

Considerando que você sabe o tempo de execução para 2¹⁰⁰⁰, é fácil determinar o tempo de execução para 2¹⁰⁰⁰⁰ sem o WolframAlpha:

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

---