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

Дано

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

Заполните таблицу максимальными значенимя n, для которых задача может быть решена за время t, если предполагается, что время работы алгоритма, необходимое для решения задачи, равно f(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 в верх таблицы.

Теперь рассмотрим 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.

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

и так далее

Все задания с простыми степенями можно решить с помощью 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

и так далее

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