n^O(1/ε) 是什么意思？

Question

3

我经常在近似算法中看到n^O(1/ε)。例如，在欧几里得TSP问题中，门户（及其可能的状态）的数量等于n^O(1/ε)。

有人能解释一下为什么3^4m = n^O(1/ε)吗？

- ryan chandra

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pasthec · Accepted Answer

一般来说，逼近算法的复杂度取决于所需精度，通常用ε表示，以表示您希望答案与最佳答案的比率之间的差异不超过ε。

这意味着时间复杂度的依赖关系在指数上，因为对于每个ε，算法都是多项式的，但随着ε越小，指数越大。也就是说，这里时间复杂度的指数作为ε的函数增长为O(1/ε)。

确实，在本文中提到：“参数m必须位于区间[k/ε，2k/ε]”，并且4^k=O(n^4)，因此3^(4m)=3^(O(k/ε))=3^(O(log(n)/ε))=n^(O(1/ε))。