下面的代码返回给定数字 n 的所有质因数。
Approach behind the algorithm:
遍历数字(即 >=2)直到 n/i 以获得质因数。
内部循环只是通过将数字除以当前素数来减少数字的大小，如果同一个素数出现不止一次，它将继续除以。
if 语句将为 n > 2 添加最后一个和最大的素数，因为到那时 n 会减少到该值。
static List<Integer> getAllPrimes(int n){
List<Integer> factors = new ArrayList<Integer>();
for(int i = 2 ; i <= n/i ; ++i){
while(n % i == 0){
factors.add(i); //LINE 1
n/=i;
}
}
if(n > 2){factors.add(n);}
return factors;
}
如何确定该算法的运行时间？由于每次迭代内部循环时，如果它是素数，它会根据索引 i 以某个常数值(例如 n/2、n/3... 等)减小大小。
最佳答案
在分析这样的算法时，弄清楚您是在寻找最佳情况、平均情况还是最坏情况分析通常很有帮助，因为每种情况下的答案可能不同。
让我们从最坏情况分析开始。要使该算法尽可能长时间地运行，必须发生什么？好吧，如果我们从不划分任何质因数，那么外层循环将运行尽可能多的次数。具体来说，它将运行 Θ(√n) 次。只有当所讨论的数字是质数时才会发生这种情况，因此我们可以说最坏的情况发生在质数输入上，其中运行时间为 Θ(√n)。
最好的情况呢？好吧，当 i 对于 n 太大或 n 对于 i 太小时，这个算法将终止。降低 n 比增加 i 快得多，因为 n 呈几何下降，而 i 呈算术增长。一个理想的情况是输入尽可能快地下降，如果您提供的输入只有很小的因子(这些称为平滑数)，就会发生这种情况。在理想情况下，您将获得 2 的完美幂，在这种情况下，算法会反复将 n 减半，直到它降至 1。这是对数行为的标志，因此在最佳情况下，运行时间为 Θ(log n).
关于java - 以下算法的执行时间是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44737962/