使用模数的 while 循环的时间复杂度
Time complexity for while loops using modulo
我需要帮助找出第一个和第二个循环（嵌套的 for-while 循环）的时间复杂度，我不太确定我的答案：
第一个循环：O(log n)
第二个循环：O(sqrt(n) logn)
代码：
public static int findLength(int n){
int length = 0;
//FIRST LOOP
while (n%2==0){
length++;
n /= 2;
}
//SECOND LOOP
for (int i = 3; i <= Math.sqrt(n); i+= 2) {
while (n%i == 0) {
length++;
n /= i;
}
}
if (n > 2)
length++;
return length;
}
第一个循环
- 第一极：
n是奇数
- 循环不运行
- 时间：
O(1)
- 第二极：
n是2的幂
- 循环运行s最大次数（相对于
n的不同值）
- 时间：
O(log n)
整体时间复杂度：O(log n)
第二个循环
第一极：n是素数
- 嵌套
while 循环根本运行
- 时间：
O(sqrt(n))
第二极值：n = (p1 ^ q1) * (p2 ^ q2) * .. * (pn ^ qn)，其中p1, p2 .. pn是素数（泛化第一个极端)
- 操作总数（不包括循环计数器 / 测试表达式）：
q1 + q2 + ... + qn
- 时间：
O(log n)
整体时间复杂度：O(sqrt(n))
我需要帮助找出第一个和第二个循环（嵌套的 for-while 循环）的时间复杂度，我不太确定我的答案：
第一个循环：O(log n)
第二个循环：O(sqrt(n) logn)
代码：
public static int findLength(int n){
int length = 0;
//FIRST LOOP
while (n%2==0){
length++;
n /= 2;
}
//SECOND LOOP
for (int i = 3; i <= Math.sqrt(n); i+= 2) {
while (n%i == 0) {
length++;
n /= i;
}
}
if (n > 2)
length++;
return length;
}
第一个循环
- 第一极：
n是奇数- 循环不运行
- 时间：
O(1)
- 第二极：
n是2的幂- 循环运行s最大次数（相对于
n的不同值） - 时间：
O(log n)
- 循环运行s最大次数（相对于
整体时间复杂度：O(log n)
第二个循环
第一极：
n是素数- 嵌套
while循环根本运行 - 时间：
O(sqrt(n))
- 嵌套
第二极值：
n = (p1 ^ q1) * (p2 ^ q2) * .. * (pn ^ qn)，其中p1, p2 .. pn是素数（泛化第一个极端)- 操作总数（不包括循环计数器 / 测试表达式）：
q1 + q2 + ... + qn - 时间：
O(log n)
- 操作总数（不包括循环计数器 / 测试表达式）：
整体时间复杂度：O(sqrt(n))