为什么这个程序这么慢？

Question

所以我想出了ProjectEuler问题29的这个解决方案(http://projecteuler.net/problem=29)

答案是对的.我希望这段代码运行得非常快,但运行速度非常慢.我不知道为什么.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<pair<int,int>> factorized_int; // pairs of base, exponent

factorized_int primeFactors(int n) {
        int primeFactors[100] = {0};
        for (int i=2; i <= n; i++) {
                if (n%i == 0) {
                        primeFactors[i]++;
                        n /= i;
                        i--;
                }
        }

        vector<pair<int,int>> retValue;
        for (int i=2; i<100; i++) {
                if (primeFactors[i] != 0) {
                        retValue.push_back(pair<int,int>(i,primeFactors[i]));
                }
        }

        return retValue;
}

factorized_int pow(factorized_int n, int exponent) {
        factorized_int retValue = factorized_int(n);
        for (size_t i = 0; i<retValue.size(); i++) {
                retValue[i].second *= exponent;
        }
        return retValue;
}

int main() {

        vector<factorized_int> list;

        for (int a=2; a <= 100; a++) {
                factorized_int factorized_a = primeFactors(a);
                cout<<a<<endl;
                for (int b=2; b <= 100; b++) {
                        factorized_int number = pow(factorized_a,b);

                        if (find(list.begin(), list.end(), number) == list.end()) {
                                list.push_back(number);
                        }
                }
        }


        cout<<list.size();
        getchar();
        return 0;
}

有任何想法吗？

编辑:我得到的大部分答案都是算法的算法复杂性.请注意,n非常低(100)并且还:

int main() {

            vector<factorized_int> list;

            for (int a=2; a <= 100; a++) {
                    factorized_int factorized_a = primeFactors(a);
                    cout<<a<<endl;
                    for (int b=2; b <= 100; b++) {
                            /*factorized_int number = pow(factorized_a,b);

                            if (find(list.begin(), list.end(), number) == list.end()) {
                                    list.push_back(number);
                            }*/
                    }
            }


            cout<<list.size();
            getchar();
            return 0;
    }

几乎立即开始.这让我觉得问题在于pow函数的O(n)中的常数.我认为在调用pow(factorized_int,int)时std :: vector的各种副本都存在问题.如何检查和优化？

注意:在我的电脑中,评论版本的运行时间不到0.1秒,第一个版本需要30秒以上

Answer 1

你不清楚'快'还是'慢'是什么,但是:

int main() {
        vector<factorized_int> list;

        for (int a=2; a <= 100; a++) { //O(a)
                factorized_int factorized_a = primeFactors(a); //O(2a)
                cout<<a<<endl;
                for (int b=2; b <= 100; b++) {  //O(b)
                        factorized_int number = pow(factorized_a,b);//O(2b)

                        if (find(list.begin(), list.end(), number) == list.end()) {
                                list.push_back(number);
                        }
                }//total of O(b*2b) => O(b^2)
        }//total of O(a * (2a + b^2)) => O(n^3)


        cout<<list.size();
        getchar();
        return 0;
}

注释大致表示函数调用的算法复杂性.你有一个O(n ^ 3),这很慢.