Блог

учитывая следующую проблему из книги алгоритмов CLRS.

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

1. как можно вычислить n для f (n) = nlog (n), когда время равно 1 секунде?
2. как можно вычислить n для f (n) = n! когда время равно 1 секунде?

Упоминается, что алгоритм занимает f (n) микросекунд. Тогда можно считать, что алгоритм состоит из f (n) шагов, каждый из которых занимает 1 микросекунду.

В заданных вопросах указано, что соответствующие значения f (n) привязаны к 1 секунде. (т.Е. 10 ⁶ микросекунд) Затем, поскольку вы ищете наибольшее возможное n для выполнения этих условий, ваши вопросы сводятся к неравенствам, приведенным ниже.

1) f (n) = nlog (n) <= 10 ⁶

2) f (n) = n! <= 10 ⁶

Остальное, я полагаю, в основном манипулирует алгеброй и логарифмическими уравнениями, чтобы найти соответствующие значения.

В первом случае вы можете обратиться к примеру метода Ньютона для вычисления кубического корня. Метод Ньютона для аппроксимации корней или функции Ламберта W. Это может помочь вычислить значение n. Согласно моим выводам, в основном, никакой другой аналитический подход не может помочь.

Во втором случае скрипт python может помочь вычислить n с помощью ручного подхода.

 def calFact(n):
    if(n == 0 or n==1):
        return n
    return n*calFact(n-1)

nVal=1
while(calFact(nVal)<1000000):         # f(n) = n! * 10^-6 sec
    nVal=nVal 1                       # 10^6 = n!

print(nVal)
  

Итак, в этом случае мы пытаемся найти n таких, что n! равно или близко к 10 ^ 6.