-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 のさまざまなコピーに問題があると思います。どうすればそれを確認して最適化できますか?

注: 私の PC では、コメント付きのバージョンは 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 に答える