多项式执行时间示例
Polynomial Execution Time Examples
下面的两个执行时间是多项式的，为什么？
I O(n^log n)
II O(log(n^n))
我相信只有 I 是多项式的，因为 II 看起来是对数的，这是正确的断言吗？
根据日志属性，log(n^n) = n * log(n) 对于大 n 小于 n^2。因此，O(log(n^n)) 包含在 O(n^2) 中，多项式时间也是如此。
n^log n 对于任何 c,k 都不能被 c * n^k 限制，因为 log n 是一个单调增长函数，所以显然它不能在多项式时间内。然而，对于足够大的 n，它小于 2^n（我将把它作为一个练习来验证），因此至多是指数级的。
下面的两个执行时间是多项式的，为什么？
I O(n^log n)
II O(log(n^n))
我相信只有 I 是多项式的，因为 II 看起来是对数的，这是正确的断言吗？
根据日志属性，log(n^n) = n * log(n) 对于大 n 小于 n^2。因此，O(log(n^n)) 包含在 O(n^2) 中，多项式时间也是如此。
n^log n 对于任何 c,k 都不能被 c * n^k 限制，因为 log n 是一个单调增长函数，所以显然它不能在多项式时间内。然而，对于足够大的 n，它小于 2^n（我将把它作为一个练习来验证），因此至多是指数级的。