r - 获取算法复杂度表的最有效方法

Question

我试图用 R 填写“算法导论，第 3 版”(麻省理工学院出版社出版)(第 14 页)中作为练习题给出的表格。

Click this link to see the table.

//下面:添加了句子，感谢 G. Bach 的评论。

我应该用

假设解决问题的算法需要 f(n) 微秒，可以在时间 t 解决的问题的最大规模 n。

//以上:添加了句子，感谢 G. Bach 的评论。

我的代码如下所示。

msec <- 1
sec <- msec * 1000000
min <- sec * 60
hour <- min * 60
day <- hour * 24
mon <- day * 30
year <- day * 365
cen <- year * 100

time_units = c( sec, min, hour, day, mon, year, cen )

time_funcs = list(
    lg_n = function(x) 2^x,
    sqrt_2 = function(x) x^2,
    itself = function(x) x,
    n_sq = function(x) sqrt(x),
    n_3sq = function(x) pracma::nthroot(x, 3),
    nsq_of_2 = function(x) log2(x)
)

obvious_vals <- sapply( time_units, plyr::each(time_funcs) )

'obvious_vals'的内容是

                 [,1]         [,2]         [,3]         [,4]         [,5]         [,6]         [,7]
lg_n              Inf          Inf          Inf          Inf          Inf          Inf          Inf
sqrt_2   1.000000e+12 3.600000e+15 1.296000e+19 7.464960e+21 6.718464e+24 9.945193e+26 9.945193e+30
itself   1.000000e+06 6.000000e+07 3.600000e+09 8.640000e+10 2.592000e+12 3.153600e+13 3.153600e+15
n_sq     1.000000e+03 7.745967e+03 6.000000e+04 2.939388e+05 1.609969e+06 5.615692e+06 5.615692e+07
n_3sq    1.000000e+02 3.914868e+02 1.532619e+03 4.420838e+03 1.373657e+04 3.159382e+04 1.466455e+05
nsq_of_2 1.993157e+01 2.583846e+01 3.174535e+01 3.633031e+01 4.123720e+01 4.484206e+01 5.148592e+01

但是，我无法获得 nlog2(n) 和 n! 的反函数(n 阶乘)。因此，我创建了一个函数来获取 n 的近似值，如下所示。(此代码仅适用于 nlog2(n)。)

get_aprx_val <- function () {
    max_iter <- 100
    threshold <- 1.0e-07
    results <- rep( NA, length(time_units) )
    index <- 1

    for ( t_unit in time_units ) {
        x <- t_unit
        step <- .5 * t_unit

        for ( i in 1:max_iter ) {
            if ( x*log2(x) - t_unit >= threshold ) {
                x <- x - step
            }
            else if ( x*log2(x) - t_unit <= -threshold ) {
                x <- x + step
            }
            else {
                results[index] <- x
                break
            }
            step <- .5 * step
        }

        index <- index + 1
    }

    results
}

虽然我通过上面的操作得到了结果，如下所示，

[1] 6.274613e+04 2.801418e+06 1.333781e+08 2.755148e+09 7.187086e+10 7.976339e+11 6.861096e+13

但我不确定我是否以最有效的方式完成了它们。有没有人有更好的主意来帮助我？

提前谢谢你。

Answer 1

如果你想使用数值优化，你可以使用uniroot:

sapply(time_units, 
       function(time) uniroot(function(n) n * log2(n) - time, c(1e-8, 1e20))$root)
#[1] 6.274613e+04 2.801418e+06 1.333781e+08 2.755148e+09 7.187086e+10 7.976339e+11 6.861096e+13

要获得更有效的方法，您必须求助于数学。