-4

所以我想出了解决 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多秒

4

1 回答 1

7

您不清楚“快”或“慢”是什么，但是：

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)，非常慢。

于 2013-07-17T20:44:17.267 回答