Big-O表示法的函数时间复杂度？

Question

1)Althoug我研究了大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)

Answer 1

使用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),依此类推.