-2

パラメータとして符号なし整数を受け取り、この数値の桁数を返す 2 つの関数を考えてみましょう。1 つの関数は再帰的で、もう 1 つは非再帰的です。

複雑さに関しては、どの実装が優れていますか?

使用言語はC/C++です。

非再帰関数は次のとおりです。

int nbOfDigitsNR(int nb) {
int i=0
while(nb!=0){
 nb=nb/10; 
 ++i;
}
return i; // i is the number of digits 
}

再帰関数:

int nbOfDigitsNR(int nb) {
 static int i;
 if (nb!=0){
 i=i+1;
 nbOfDigitsNR(nb/10);}
 return i;
}

時間の複雑さは同じ O(n) であり、空間の複雑さは異なる O(n) 再帰的であることをお勧めします。O(1) 非再帰。

4

2 に答える 2

1

関数が再帰的または非再帰的であると言っても、その複雑さについては何もわかりません。

それは等しいか、複雑さが低いものの1つである可能性があります..それは完全にアルゴリズムに依存します.

青とグレーの車を持っています。どちらが速いですか？

于 2015-04-26T18:29:00.147 に答える