用Big-O符號表示函數的時間複雜度？

1）Althoug我研究過大O符號，我無法理解我們如何根據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)

來源

2013-05-01 mxyz

提前開始位置1個字符，減少結束位置1個字符（因爲它們匹配或它不是迴文） - 不同的是2個字符的長度。另一個函數簽名可能是'bool isPalindrome（char * start，char * end）'。 – user2246674 2013-05-01 17:47:29

很確定這是O（n），因爲它調用它自己與字符串的長度有關。 – 2013-05-01 17:51:11

***你對O（n）的計算有什麼不瞭解？ – phant0m 2013-05-01 17:51:58

與您通話的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 n）如果存在常數c和數目n 0，則函數g（n）是O（f（n）），從而對於n * n（n）爲012 * c * n（n）。大O符號只是一個上限，所以函數是O（n）而且是O（n^2）等等。

來源

2013-05-01 17:48:58

你是怎麼想出n^2的？每個長度最多隻能調用一次 - 不變。 – 2013-05-01 17:53:26

@MichaelDorgan它是一個* upper * bound;） – phant0m 2013-05-01 17:53:53

@red_eyes您使用大O的方式與我教過的不同。據我推測，這個算法是O（n），沒有別的。 – john 2013-05-01 18:40:51

函數以長度爲n的字符串開始，每次在循環中將其減少2，直到它全部減少爲止。

因此迭代次數與長度2成正比，即O(n/2) =>O(n)。

來源

2013-05-01 17:55:47

用Big-O符號表示函數的時間複雜度？

回答

相關問題