Максимальное значение 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 код | |
Виды копирования | |
LBYL vs EAFP | |
Make |