下面函数可以将 n 的所有质因数找出来，其时间复杂度是（）。 #include #include vector get_prime_factors(int n) { vector factors; while (n % 2 == 0) { factors.push_back(2); n /= 2; } for (int i = 3; i * i 2) { factors.push_back(n); } return factors; }

以下C++实现的质因数分解函数的时间复杂度是？

up337240 单选题共个子题

下面函数可以将 n 的所有质因数找出来，其时间复杂度是（）。

#include <iostream>
#include <vector>

vector<int> get_prime_factors(int n) {
    vector<int> factors;

    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

    if (n > 2) {
        factors.push_back(n);
    }

    return factors;
}

$O(n^2)$

$O(n\log n)$

$O(\sqrt{n}\log n)$

$O(n)$

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析

讨论

发布

登录后参与讨论

立即登录

发布讨论需先绑定并验证手机号

去绑定手机号

加载中…

我

回复 @

发送

还没有人讨论，来发表第一条吧

New