使用oracle有效地对整数进行素分解
假设您有一个程序one_factor（N），给定一个n数字二进制数，N，返回Theta（n^2）时间中数字的质因数之一（注意，我在θ符号中使用了小写n。）
使用这个算法，我想找到一个有效的算法，将一个n-位二进制数分解为素数并打印素数因子。此外，我想知道算法作为n的函数运行的速度有多快，我还想计算我的算法在最坏情况下使用one_factor（n）oracle作为
假设Θ（n）时间加/除/乘/减两个n位二进制数。
下面是一个有效的算法：
-
< li >调用< code>one_factor(N)。如果函数返回< code>N，那么< code>N是质数，我们就完成了。否则，把这个质因数分出来，存放在某个地方。重复这个过程，直到我们完成。
现在，我在分析此过程的运行时作为n的函数时遇到问题。为了简单起见，如果N是2的幂，那么n = log_2（N），但我真的不太确定如何从这里开始。
我不明白如何找到我们调用one_factor的最坏情况次数，而且我也无法分析最坏情况运行时间。
共有2个答案
请注意，除法后，您的数字N变为N /2或更小。因此，您最多需要 log2（N） 预言机调用。这是 O（n）。每次调用都需要O（n²）时间或更少（根据您对O的定义，可能需要提及“更少”）。
如果你的N是2的幂，它实现了调用次数的最坏情况。幸运的是，它还意识到了每次调用执行时间的最坏情况，因为在它们的前半部分，这个数字足够大——它至少有n/2位数。
首先，神谕很精彩，但速度很慢。所以你想先尝试做审判除法。
从维基百科的算术函数中，如果你使用牛顿-拉夫森除法和哈维-霍文算法，可以及时检查你是否被素数整除p。计算O（n/log（n））素数到n是可行的，Eratothenes的筛选时间远小于
现在你提到你的神谕。每个预言机都需要时间，与之相比，除法很小。它将数字的大小至少减少一个因子n。需要如何划分O（log_n（2^n））=O（log（2|n）/log（n））=O（n/log，n））。根据上述相同算法，每个除法都是O（n log（n））。
得到的算法是O（n^2*（n*log（n））*n/log（n”）=O（n*4）。请注意，/log（n）是在必须咨询oracle之前进行试算的节省。
请注意，你不能通过进行更多的试除法来改善这一点，因为如果你试图遍历所有的素数直到n^2，你在试除法上花费的时间比你原来的算法要多，并且甲骨文除法部分的big-O仍然是相同的。
-
问题内容： 令我惊讶的是，以前没有提出过这个具体问题，但我的确没有在SO或文档中找到它。 假设我有一个包含整数的随机numpy数组，例如： 如果对它进行排序，则默认情况下我将获得升序： 但我希望解决方案按 降序 排序。 现在，我知道我可以永远做： 但这最后的陈述 有效 吗？它不是按升序创建副本，然后反转此副本以反转顺序获得结果吗？如果确实如此，是否有有效的选择？看起来好像不接受参数来更改排序操作中
-
本文向大家介绍对Java对象数组进行分组的最有效方法，包括了对Java对象数组进行分组的最有效方法的使用技巧和注意事项，需要的朋友参考一下 在js中对象数组上按键分组的最有效方法是使用reduce函数。 该方法在数组的每个元素上执行reducer函数（由您提供），从而产生单个输出值。 示例 输出结果 这将给出输出-
-
给定一个数N，我需要找到从1到N至少有一个素数（2,3,5或7）的数的计数。 现在N可以高达10^18。解决这个问题的最佳方法是什么。 例句：设N=100，答案是64。 请帮助解决这个问题。 代码：这是主要功能，但显然不是好方法
-
我需要在颠簸转换规范方面的帮助。以下是我到目前为止的工作。 输入： 使用的震动代码： 电流输出： 预期产出 当只使用单个json对象时，此代码工作正常。但是当我们使用具有相同id的多个项目时，它会开始对所有相关字段进行分组。
-
我想在RESTful API中支持分页。 我的API方法应该通过返回产品的JSON列表http://localhost/products/v1/getproductsbycategory，可能有数千种产品，我想翻阅它们，因此我的请求应该如下所示：
-
问题内容： 我搜索并没有找到解决该问题的Go解决方案，无论是否使用，都没有，也没有在其他任何站点上。 假设我们在Gogo中建模了一个MongoDB集合： 我们希望根据某些条件对用户进行排序和列出，但是由于预期结果列表较长，因此已实现了分页。 为了实现对某些查询结果的分页，MongoDB和驱动程序包以和的形式内置支持，例如： 但是，如果页数增加，这将变得很慢，因为MongoDB不能仅“神奇地”跳到结