友善的数字：运行时间太长。是什么原因造成的？算法复杂度？

Question

我的代码运行有点时间问题。代码工作正常，除了 Windows 需要几十分钟，Linux 到运行.

需要几个小时

class AmicableNumbersBeta
{
private:
    long start;
    long end;
    std::vector<long> numbers;

protected:

    long getStart() { return start;}
    long getEnd() { return end;}

    void setStart(long start) {  this->start = start;}
    void setEnd(long end) {  this->end=end;}

    long SumOfDivisors(long value)
    {
        long result = 0;
        long half_value = value / 2;

        for (long i = 1; i <= half_value; i++)
        {

           if (value % i == 0)
           {
             result += i;
           }
        }

        return result;
    }

    void AddNumber(long value)
    {
        this->numbers.push_back(value);
    }

public:

    AmicableNumbersBeta(long Start, long End) : start(Start),end(End){}


       void Calculate()
       {
       // clear old calculation, if any
       this->numbers.clear();


       for (long i = getStart(); i < getEnd(); i++)
       {

           long s1 = SumOfDivisors(i);
           long s2 = SumOfDivisors(s1);

           if (s2 == i && i < s1)
           {
            std::cout<<"-- adding ( "<<i<<" )\n";
            this->AddNumber(i);
           }
       }
    }

};

如果我现在尝试运行这个程序，它开始计算 Alpha 直到 1000000 个数字并检查它需要几个小时。 但据我的老师说，计算应该只需要几秒钟。

int main() {
std::cout << "Hello, World!" << std::endl;

AmicableNumbersBeta Alpha(1,1000000);
AmicableNumbersBeta Beta( 1,100000);
AmicableNumbersBeta Gamma(1,10000);
AmicableNumbersBeta Delta(1,1000);

std::cout<<"Delta\n";
Delta.Calculate();

std::cout<<"\nGamma\n";
Gamma.Calculate();

std::cout<<"\nBeta\n";
Beta.Calculate();

std::cout<<"\nAlpha\n";
Alpha.Calculate();

std::cout << "Bye, World!" << std::endl;
return 0;
}

老实说，我不明白是什么导致了这个巨大的 "delay"。

我使用的平台是 Linux Debian with GCC 4.9 Windows VS 15

如果有人能指出这种行为的原因，我将不胜感激。

Answer 1

如评论中所述，您的代码可以通过使用 memoization or sieves 甚至并行性以多种方式进行优化。

虽然在实际应用程序中，我可能会进行此类优化，但您在这里不需要此类 "complex" 东西 - 您只需进行一次改进即可在几秒钟内使您的代码运行而不是分钟：您只需要计算除数直到您的值的平方根。所以基本上：

long SumOfDivisors(long value)
{
    long result = 1; 

    for (long i = 2; i * i <= value; i++)
    {
       if (value % i == 0)
       {
           result += i;
           if (value / i != i) {
               result += value / i;
           }
       }
    }

    return result;
}

通过这个简单的修改，您可以在几秒钟内计算出高达 1000000 的友好数。

友善的数字：运行时间太长。是什么原因造成的？算法复杂度？

Amicable Numbers: Runtime is to long. What could cause that? algorithm complexity?

c++

math

runtime