0

1）尽管我已经研究过大 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

您使用 len-2 调用递归函数，因为在每次执行中，您从单词中删除 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 ) 如果存在常数 c 和数字 n0，则函数 g(n) 为 O(f(n))，因此对于 n>n0 g(n) < c*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 回答