大O的運行時間功能

Question

找到大O運行時間爲每個功能：

1. T(n) = T(n - 2) + n²
   我們的答案：n²，n³
2. T(n) = 3T(n/2) + n
   我們的答案：O(n log n)，O(nlog₂3)
3. T(n) = 2T(n/3) + n
   我們的答案：O(n log base 3 of n),O(n)
4. T(n) = 2T(n/2) + n^3
   我們的答案：O(n³ log₂n)，O(n³)

因此，我們無法決定對每個問題的正確答案。

我們都得到了不同的結果，並且希望在什麼運行時間將是外界輿論。

在此先感謝。

Answer 1

澄清的位：
在問題的功能似乎是運行時間功能通過T()名字和他們n參數作爲暗示。一個更微妙的提示是，它們都是遞歸的，遞歸函數是一個常見事件，當我們生成一個函數來描述一個算法的運行時間時（即使算法本身沒有正式使用遞歸）。事實上，遞推公式是很不方便的形式，這就是爲什麼我們使用大O符號，以更好地總結了算法的行爲。

運行時間函數是參數（或多個）參數化一個數學表達式，其允許計算用於一個算法的運行時間[有時近似]相對值，給定的特定值（S）。比如這裏的情況下，運行時間函數通常只有一個參數，通常命名n，對應的項目算法，預計總人數與搜索算法上下工夫/帶（對於例如，它可能是總數據庫中的記錄數，使用排序算法可以是未排序列表中的條目數和路徑查找算法的數量，圖中節點的數量....）。在一些情況下，運行時間函數可以具有多個參數，例如，在圖形上執行某些變換的算法的性能可結合到兩個節點的總數和頂點的總數量或連接的平均數目兩個節點之間，等等

在手（對於這似乎是家庭作業，因此我的部分答案），因此，找到一種Big O表達有資格每個運行時間函數的上邊界限制的任務，，無論它們可能對應的底層算法是什麼。任務是不，尋找和排位賽的算法產生的函數的結果（這第二個可能性也是鍛鍊算法班CS的cursus的一個很常見的類型，但顯然不是什麼這裏需要。）

因此，問題是計算機科學本身的數學問題之一。
基本上，當n接近無窮大時，需要找到每個函數的極限（或其近似值）。
這note from Prof. Jeff Erikson在伊利諾伊大學厄巴納香檳分校提供一個很好的介紹，以解決復發。
雖然解決復發有一些捷徑，特別是如果一個人有一個良好的微積分命令，一個通用的方法是猜測答案，然後通過歸納證明。諸如Excel之類的工具，諸如Python之類的編程語言中的一些片段，或MATLAB或Sage可用於產生前幾百個值（或超出）的表以及諸如n^2，n^3，n之類的值！以及功能條款的比例;這些表通常提供足夠的洞察函數來查找函數的封閉形式。
功能a）
    O(n^2)是肯定錯了：

關於答案的幾個提示的問題上市
       前幾個值的序列中的快速檢查顯示n^2比T（n）更加小得多
    O(n^3)另一方面似乎系統地大於隨着n向大數字增長，。仔細看，O(n^3)實際上是該函數的大O符號的命令，但是O(n^3/6)是系統地超過T（n）的值的更精確的符號[對於更大的n值和/或作爲n傾向於無窮大]，但僅與更粗略的n^3估計值相比分數部分。
一個可以確認O(n^3/6)是，通過感應：

T(n) = T(n-2) + n^2 // (1) by definition 
T(n) = n^3/6  // (2) our "guess" 
T(n) = ((n - 2)^3/6) + n^2 // by substitution of T(n-2) by the (2) expression 
    = (n^3 - 2n^2 -4n^2 -8n + 4n - 8)/6 + 6n^2/6 
    = (n^3 - 4n -8)/6 
    = n^3/6 - 2n/3 - 4/3 
    ~= n^3/6  // as n grows towards infinity, the 2n/3 and 4/3 factors 
        // become relatively insignificant, leaving us with the 
        // (n^3/6) limit expression, QED