数生成アルゴリズムがあり、その時間計算量を知りたいですか？
長さnまでのすべての組み合わせを生成します。
以下はコードスニペットです
void generate_N_Numbers(int n){
int len = 0;
int alphaLen = 2;
int *letters = malloc(n * sizeof(int));
uint64_t outerLoopCounter = 0,innerLoopCounter1 = 0,innerLoopCounter2 = 0,
innerLoopCounter3 = 0,innerLoopCounter4 = 0,totalLoopCounter = 0;
for (len=1; len<=n; len++)
{
outerLoopCounter++;
int i;
int stride = len+1;
int bufLen = stride * alphaLen * alphaLen;
if (len == 1)
continue;
for (i=len-2; i<bufLen; i+=stride)
innerLoopCounter1++;
if (len == 2)
continue;
for (i = 0; i < len;i++){
letters[i] = 0;
innerLoopCounter2++;
}
i = len-3;
do {
int j;
innerLoopCounter3++;
letters[i]++;
if (letters[i] >= alphaLen)
letters[i] = 0;
for (j=i;j<bufLen;j+=stride){
innerLoopCounter4++;
}
if (letters[i] != 0) {
i = len - 3;
continue;
}
i--;
if (i < 0)
break;
} while(1);
}
}
このコードへのリンクは次のとおりです。https://ideone.com/HxzDGv
入力1から30のアルゴリズムの結果へのリンクは次のとおりです。https：//pastebin.com/LwavAff1
その複雑さはO（n2）だと思いますが、それでもこれについてはよくわかりません。そして、このループは、どういうわけかO（n）の時間計算量を持つループよりも速く数を生成します。
はい、実行時間がO（n ^ 2）になると仮定するのは正しいです。考慮すべきコードの最もコストのかかる部分は、2つのループ内の部分です。他のすべてのセクションは重要ではなく、O（1）の時間がかかります。
外側のforループはn回実行され、内側のforループはそれぞれO（n）回実行されます。
あなたのdo-whileループは、以下をn回実行し、forそのループ内側には、ほとんどのn回で実行されます。
最も内側のforループ内のすべての操作はO（1）であることに注意してください。
この情報を要約すると、n *（n * 1 + n * 1）+ n * n * 1の演算、つまりO（n ^ 2）が必要です。
注：あなたのコードは非常に混乱しているので、私はあなたがしていることの背後にある論理に従うことを試みませんでした。基本的な複雑さの分析を示したかっただけです。をご覧になることをお勧めしstd::next_permutationます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加