拉托斯特尼筛法(试除法)是多项式算法吗
如题,按照分析来说应该属于啊,为什么别人都说不是 算法
[解决办法]
严格来说复杂度是关于输入的长度的函数。假设输入的数字是n的话,输入的长度实际是O(logn),因此只有关于n的对数多项式才是关于输入长度的多项式。筛法至少有个O(n),关于logn已经是指数了。
发布时间: 2013-08-01 15:23:18 作者: rapoo
拉托斯特尼筛法(试除法)是多项式算法吗
如题,按照分析来说应该属于啊,为什么别人都说不是 算法
[解决办法]
严格来说复杂度是关于输入的长度的函数。假设输入的数字是n的话,输入的长度实际是O(logn),因此只有关于n的对数多项式才是关于输入长度的多项式。筛法至少有个O(n),关于logn已经是指数了。