0

1) Big-O 記法について調べましたが、Big-O 記法でこの関数の時間計算量を計算する方法を理解できませんでした。詳しく説明していただけますか。

2) 再帰関数の場合。再帰関数を使用しているときに len-2 を呼び出すのはなぜですか?

bool isPalindrome( char *s, int len) {
             if (len <= 1) {
             return true;
        }
             else
            return ((s[0] == s[len-1]) && isPalindrome(s+1,len-2));
        }

Big-O 表記で表したこの関数の時間計算量はどれくらいですか?

T(0) = 1 // base case
T(1) = 1 // base case
T(n) = 1 + T(n-2)// general case
T(n-2)=1+T(n-4)
T(n) = 2 + T(n-4)
T(n) = 3 + T(n-6)
T(n) = k + T(n-2k) ... n-2k = 1  k= (n-1)/2
T(n) = (n-1)/2 + T(1)  O(n)
4

2 に答える 2

5

各実行で単語から 2 文字 (最初と最後) を削除するため、再帰関数を len-2 で呼び出します。したがって、len-2 です。T(n) = 1 + T(n-2) = 1 + 1 + T(n-4) = 1 + 1 + 1 + T(n-6) = n/2 + T(1) = O(n ) 関数 g(n) は、n>n0 に対して g(n) < c*f(n) となる定数 c と数 n0 が存在する場合、O(f(n)) です。big-O 表記は単なる上限であるため、関数は O(n) ですが、O(n^2) などもあります。

于 2013-05-01T17:48:58.227 に答える
1

この関数は長さ n の文字列で始まり、すべてが縮小されるまで、ループのたびに文字列を 2 ずつ縮小します。

したがって、反復回数は長さ/2、つまりO(n/2)=>に比例しO(n)ます。

于 2013-05-01T17:55:47.060 に答える