函数的时间复杂度分析

Question

下面这个函数的时间复杂度是多少？我对 O(log n) 和 O(sqrt(n)) 感到困惑。

map<long long int,long long int> mp;
void PrimeFactorization(long long n)
{
    while(n%2==0)
    {
        n/=2;
        mp[2]++;
    }
    for(long long int i=3;i<=sqrt(n)+1;i+=2)
    {
        while(n%i==0)
        {
            n/=i;
            mp[i]++;
        }
    }
    if(n>2)
    {
        mp[n]++;
    }
}

Answer 1

这在 O(sqrt(n)) 中运行。 技术上，它是 O(sqrt(n) + log(n)log(log(n)))，但是 log 因素并不是什么大问题（您可以通过使用无序映射来摆脱它） .

想想最坏的情况：如果 n 是素数，那么从 3 到 sqrt(n) 的循环将一直旋转到它的极限。这甚至算不上什么极端情况，因为素数相当普遍。实际上，循环只是在搜索 n 的所有质因数，所以它有上升到 sqrt(n) 因为那是质数的极限因素。

还有其他更快的素因数分解算法。查看 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 和 https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

函数的时间复杂度分析

Time Complexity Analysis of a function

c++

time-complexity