Максимальное значение n для которых задача может быть решена за время t

Содержание
Дано
Таблица
Решение
Python скрипт
Ответ
Другие статьи о С++

Дано

Ниже приведена таблица, строки которой соответствуют различным функциям f(n), а столбцы - значениям времени t.

Заполните таблицу максимальными значенимя n, для которых задача может быть решена за время t, если предполагается, что время работы алгоритма, необходимое для решения задачи, равно f(n) микросекунд.

Таблица

СекундаМинутаЧасДеньМесяцГодВек
lg(n)
sqrt(n)
n
n*lg(n)
n^2
n^3
2^n
n!
n^n

Решение

Первым делом нужно понять вопрос. Допустим, на интересует столбец Минута что туда писать?

Найти максимальное n, при котором задача решается за минуту.

По сути мы решаем уравнение

f(n) = Минута

Где n в микросекундах, то есть правую часть тоже нужно перевести в микросекунды

Минута это 60 * 1000000 = 6 * 10^7 микросекунд

f(n) = 6 * 10^7

Важно начать решать эту задачу с самого простого задания. Составители специально спрятали его в середину таблицы.

Самый простой случай это f(n) = n

n = 6 * 10^7

Получается, что строку с f(n) = n заполнить очень леко - нужно просто перевести все временные отрезки в микросекунды

СекундаМинутаЧасДеньМесяцГодВек
n 1000000 60000000 3.6 * 10^9 8.64 * 10^10 2.592 * 10^12 3.1536 * 10^13 3.1536 * 10^15

Советую перенести строку с n в верх таблицы.

Теперь рассмотрим f(n) = n^2

Начнём с секунды

n^2 = 10^6
n = 10^3

Минуты:

n^2 = 60 * 10^6
n = sqrt(60) * 10^3 = sqrt(15) * 2 * 10^3 = 3.872983346 * 2000 = 7745.966692415

В задаче не сказано, что n должно быть целым, но для единообразия ответов сделаем такое допущение. Если есть возможность - лучше уточнять у задающего.

округляем в нижнюю сторону (*), так как нужно максимальное n которое меньше заданного времени.

(*) NB: n могло бы равняться не 7745.966692415 а немного другому занчению - это зависит от точности, с которой был вычислен квадратный корень из 15.

Если вы уверены в этой точности - можете быть спокойны. Если в похожем примере будет очень близкое значение - понять куда округлять будет непросто.

и так далее

СекундаМинутаЧасДеньМесяцГодВек
n 1000000 60000000 3.6 * 10^8 8.64 * 10^10 2.592 * 10^12 3.1536 * 10^13 3.1536 * 10^15
n^2 1000 7745 60000 29.39*10^2 1.6*10^5 5.61*10^6 5.61*10^8

Все задания с простыми степенями можно решить с помощью Python скрипта

Рассмотрим f(n) = 2^n

2^n = 1000000
n = log2(1000000)

Решение на Python

# Для вызова pow() импортируем math import math # Временные отрезки в микросекундах times = [ 1000000, 60000000, 3600000000, 86400000000, 2592000000000, 31536000000000, 3153600000000000 ] # Степени: 0.5 это квадратный корень deg = [ 1, 0.5, 1/3, 2 ] for d in deg: print(f"f(n) = n^{d}\n") for t in times: a = pow(t, d) print(a) print("f(n) = 2^n") for t in times: l = math.log(t, 2) print(l)

lg(n)

Рассмотрим f(n) = lg(n)

Секунда

lg(n) = 1000000

Здесь надо понимать, что ,например, при n = 10 время работы = 1 микросекунде

10^lg(n) = 10^1000000

n = 10^10000000

Минута

10^lg(n) = 10^60000000
n = 10^6000000

и так далее

СекундаМинутаЧасДеньМесяцГодВек
lg(n) 10^1000000 10^60000000 10^(3.6 * 10^9) 10^(8.64 * 10^10) 10^(2.592 * 10^12) 10^(3.1536 * 10^13) 10^(3.1536 * 10^15)

n ^ n

Функцию f(n) = n ^ n полезно рассмотреть до решения задачи с функцией f(n) = n * lg(n)

Написать функцию, которая будет вычислять n довольно легко на Python

import math # n * lg(n) # Решаем задачу n^n = time # где time это наши значения из списка times = [ 1000000, 60000000, 3600000000, 86400000000, 2592000000000, 31536000000000, 3153600000000000 ] # Точность, с которой хотим получить время # 1 значит, что для 1000000 и 999999 и 1000001 # будут считаться достигнутым результатом precision = 1 def nn(n, incr, bestdelta, bestn, goal, prec, step, steps): while step < steps: step += 1 if step >= steps: return (bestn, bestdelta) algtime = pow(n, n) # print(f"n = {n} algtime = {algtime}") delta = algtime - goal if delta == 0: # print(f"precise answer is n = {n}, {n}^{n} = {algtime} = {goal}") return (n, delta) elif abs(delta) <= prec: # print(abs(delta)) # print(f"high precision answer is n = {n} algtime = {algtime}") return (n, delta) elif delta < 0: # print(f"delta < 0 n = {n}") n+=incr else: if delta < bestdelta: bestdelta = delta bestn = n else: pass # print(f"delta = {delta}") n = n - incr incr = incr/10 return nn(n, incr, bestdelta, bestn, goal, prec, step, steps) for t in times: print(nn(1, 1,t , 1, t, 1, 0, 500)[0])

n * lg(n)

Рассмотрим f(n) = n * lg(n)

n * lg(n) = 1000000

10^(n * lg(n)) = 10^1000000

n^n = 10^10000000

Минута

10^(n * lg(n)) = 10^60000000
n^n = 10^6000000

и так далее

Получается задача аналогичная f(n) = n^n но для больших чисел. Причём настолько больших, что предыдущий скрипт не осилит даже секунду.

Нужен другой подход, пробуем подставить lg в основание

n * lg(n) = 1000000

lg(n * lg(n)) = lg(1000000)

lg(n * lg(n)) = 6

lg(n) + lg(lg(n)) = 6

Такую задачу решить численно гораздо проще

import math times = [ 1000000, 60000000, 3600000000, 86400000000, 2592000000000, 31536000000000, 3153600000000000 ] lgtimes = [math.log(t, 10) for t in times] # print(math.log(32, 2)) x = 12.22343383838 print(math.log(x, 2)) a = 1 n = 10 incr = 10 precision = 0.001 steps = 9999999999 def findn(lgt, steps): a = 1 n = 1000 incr = 10000000000 precision = 0.1 while a < steps: l = math.log(n, 10) # print(type(l)) # print(l) ll = math.log(l, 10) suml = l + ll delta = lgt - suml # print(f"n = {n} suml = {suml} delta = {delta}") if delta == 0: print(f"precise solution n = {n}") a = steps + 1 return n elif abs(delta) < precision: # print(delta) print(f"high precision solution n = {n}") a = steps + 1 return n elif delta > 0: a+=1 n+=10 else: n-=incr incr = incr/10 for t in times: lgt = math.log(t, 10) nm = findn(lgt, steps) print(f"t = {t}, lg(t) = {lgt}, n = {nm}")

Результаты для секунды минуты и часа, того же порядка, но отличаются от результатов wolframalpha 153200 6964830 335412040

Wolframalpha 189481, 8.6493 * 10^6, 4.17597 * 10^8

Ответ
СекундаМинутаЧасДеньМесяцГодВек
n 1000000 6 * 10^7 3.6 * 10^9 8.64 * 10^10 2.592 * 10^12 3.1536 * 10^13 3.1536 * 10^15
n^(0.5) 1.0 * 10^12 3.6 * 10^15 1.296 * 10^19 7.46496 * 10^21 6.718464 * 10^24 9.94519296 * 10^26 9.94519296 * 10^30
n^2 1 * 10^3 7.745 * 10^3 6 * 10^4 2.93938 * 10^5 1.609968 * 10^6 5.615692 * 10^6 5.6156922 * 10^7
n^3 100 391 1532 4420 13736 31593 146645
2^n 19 25 31 36 41 44 51
lg(n) 10^(10^6) 10^(6 * 10^7) 10^(3.6 * 10^8) 10^(8.64 * 10^10) 10^(2.592 * 10^12) 10^(3.1536 * 10^13) 10^(3.1536 * 10^15)
n * lg(n) 153200 6964830 335412040
n ^ n 7.066 8.41 10.647 11.644 9.689 12.361 13.653
n!
Похожие статьи
Теория
Программирование
Boilerplate код
Виды копирования
Make

Поиск по сайту

Подпишитесь на Telegram канал @aofeed чтобы следить за выходом новых статей и обновлением старых

Перейти на канал

@aofeed

Задать вопрос в Телеграм-группе

@aofeedchat

IT

Образование

Актуально сейчас

Разное

Поиск по сайту

Подпишитесь на Telegram канал @aofeed чтобы следить за выходом новых статей и обновлением старых

Перейти на канал

@aofeed

Задать вопрос в Телеграм-группе

@aofeedchat

Контакты и сотрудничество:
Рекомендую наш хостинг beget.ru
Пишите на info@urn.su если Вы:
1. Хотите написать статью для нашего сайта или перевести статью на свой родной язык.
2. Хотите разместить на сайте рекламу, подходящуюю по тематике.
3. Реклама на моём сайте имеет максимальный уровень цензуры. Если Вы увидели рекламный блок недопустимый для просмотра детьми школьного возраста, вызывающий шок или вводящий в заблуждение - пожалуйста свяжитесь с нами по электронной почте
4. Нашли на сайте ошибку, неточности, баг и т.д. ... .......
5. Статьи можно расшарить в соцсетях, нажав на иконку сети: