Обчислення часу виконання 2 ^ N функцій - алгоритм

Для домашнього завдання мені запропонували обчислити тривалість виконання різних алгоритмів. Частина, яка перешкоджає мені, - це 2 ^ N, оскільки розмір N настільки великий.

Припускаючи, що алгоритм 2 ^ N з розміром даних N = 1000 займає 5 секунд для виконання, обчислення часу виконання для розмірів даних {2000, 3000, 10000}

Тепер, 2 ^ 2000/2 ^ 1000 = 2 ^ 1000 за властивістю поділу експонента. Результат складається з 5.071509е + 301 секунд для виконання набору даних з 2000 елементів.

Як я можу вказати номер для наступних двох розмірів? 2 ^ 2000 і 2 ^ 9000 обидва повертають нескінченність у будь-якому калькуляторі, який я використовую. Професори натякають, що 2 ^ 10 приблизно до 10 ^ 3, що означає, що 1024 приблизно до 1000.

Відповіді:

1 для відповіді № 1

Функція складності часу f (N) = c * 2^N.

Оскільки f (1000) = 5, ми можемо вирішити для c = 5/2¹⁰⁰⁰.

Отже, f (N) = 5 * 2^{N - 1000}, і f (k * 1000) = 5 * 2^{(к - 1) * 1000}.

Блокрада, здається, з розрахунку 2^н, тому я допоможу вам на цьому.

Я візьму один з ваших прикладів, щоб продемонструвати метод:

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

Це використовує підказку вашого вчителя, ще один спосіб обчислення числа точніше:

2¹⁰⁰⁰ = 10^{1000 * журнал₁₀2} = 10^301.03 = 10^0.03 * 10³⁰¹ = 1.0715e301

(Як ви бачите, більш точний метод буде в 10,7 рази більше, ніж результат приблизного методу)

---

1 для відповіді № 2

Очевидно, ви не пробували WolframAlpha:

2^9000 = 1861919823602446870051646947443265806218680881620164150161309755333181392347475969737916885903925979688282376725245050928552019850699830936678289110574564545897808148390669479768088103164174862614314896361751492419355200744919106773071079582599147802839706215610874713577461171484389014531465527630202236883843662826326484204605969450292309212479576754101484210438029392847117393209646612418243468945316443055403112189769994194382253211069075682210324665380367163398351260390065146550963353638226230571087153090476005831034463871223599543367440127371321307935600294235235555686651194174520755709233252147269712646152398661272615394330256766919854213808655136454478279520538925315159120689449046824765276993871084725126289174642261134186532952389529497451225294280309592333118547431857834022107299493307642886550035108349812538868548204110949267007844894921304724439232280030484032946555862021618822463975371563390466476093942333021906014621095132521668771544547398222309222385454252810109269995041305909748903485123565191403462125774254093965366838199092942669763234497755795922782368415391408328615941087687168142703569478330639528167193433105543630476588701348505543567751790789117717660152741734303989082897740369036292716627460893145378475903236426283709902853825833522685221030263417298462852391838147572583018386475574242223720125609852369550108535609838296845885540331405153336504029657425852682616998765068978970510668576704757343969900471616618487531217423608126248306049345412199702325217046285213249285846153975313978242675003402962824121160875928608618335006217051712260195130737083017631349816669929159176667868417353866905513835554999462637481342721400975639504482716709384155856026263304270260886740810287158032302083388891446551907198669473320114371718138443660594911466234734942910722449045244457975320043694169261701681656148362205170532994281152576853709669767416127252738437485793910219846836498268031157261792859230067295449184914230926461991700842371010236588596679342492743911615365711320743215987995901101163306076544568626531198809370907612331483471833845958618077480217892890533116603350040147116218227928732817945323636422047507156427135297222275812678187736036773320854938458989641651199078792658709405149957007882875374868180442468709128120647047303125901843060904208622152998500617510802742432155144605848971282208131749602408191808406410632175265171306237793956570406435402345476628467209068729893134433124291187516075267594298323098487990166243403468912628117388443154921474663149036640983804471509564893426039130480070632369458141251485052936042164865777219873983089572387511794739572152294019631222145910901210840561445507713655658889336373566800391206925212386456974315749376

Що стосується підказки:

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

Враховуючи, що ви знаєте час виконання для 2¹⁰⁰⁰, легко визначити час виконання для 2¹⁰⁰⁰⁰ без WolframAlpha:

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

---